Let $k\geq3$. Assume graph $G$ has $m$ edges and all its maximal cliques have size $k$. What is the maximum number of maximal cliques $G$ can have? I'm mostly interested in the behavior when $m$ goes to infinity.
4
-
$\begingroup$ In very special case, when k = 1, then you can have as many clicks as you want, because you say nothing about graph connectness, nor about number of nodes. $\endgroup$– kerzolCommented Nov 4, 2017 at 23:29
-
$\begingroup$ Stupid, but just in case, when k = 2, the max number of cliques is m, take a path containing m+1 nodes for example. $\endgroup$– kerzolCommented Nov 4, 2017 at 23:34
-
$\begingroup$ Hoping that we'll see a general pattern, let me continue this sequence of these simple cases. For K = 3, the triangular grid looks like a not too bad candidate, because we reuse all edges at lest twice. However it's not optimal packing of triangles, some wrapped triangular grids should be considered. $\endgroup$– kerzolCommented Nov 4, 2017 at 23:39
-
$\begingroup$ Ok. Assume $k\geq3$. $\endgroup$– maxdan94Commented Nov 4, 2017 at 23:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
- $k=1$, the number of 1-cliques is unbounded
- $k=2$, the $P_{m+1}$ or complete (almost) balanced bipartite graphs are optimal and contains $m$ 2-cliques
- $k=3$, the simple googling gives us the following paper The maximum number of triangles in a $K_4$-free graph.
- For general $k$, Turán graph $T(n,r)$ have maximal number of $k$-cliques. Being $k$-partite graph, the Turán graph obviously do not contain any (>k)-cliques.
Turán theorem (1941) and Zykov theorem (russian paper from 1947, stated for example here), is a good starting point for concrete calculations:
Zykov theorem For all integers $k \ge \ell \ge 0$, the maximum number of $\ell$-cliques in a graph with $n$ vertices and no $(k + 1)$-cliques is ${{k}\choose{\ell}} \left(\frac{n}{k}\right)^\ell$.
It seems that Turán graph not only maximises the number of cliques in qustion but also minimizes the number of nodes. So, now the question is about whether or not the Turán graph maximises the number of cliques when we fix not $n$ but the total number of edges. unfortunately, I do not see why.
It rises another interesting question: how many different $k$-colorable graphs containing the maximal number of $k$-cliques we have? how many nodes such graphs may contain?
