The maximum number of $k$-cliques of 7-connected 1-planar graphs
In 2023, Gollin, Hendrey, Methuku, Tompkins and Zhang determined the maximum number of cliques in general 1-planar graphs with order $n$. Their extremal examples have connectivity at most three, except for a few small orders. At the high-connectivity end, we prove that every $n$-vertex 7-connected 1-planar graph has at most $4n-12$ edges, $4n-16$ triangles, and $n-6$ copies of $K_4$. Hence the total number of cliques is at most $10n-33$. All bounds are sharp for infinitely many values of $n$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.06378
curl -X POST /api/v1/records/arxiv/2605.06378/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.06378/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'