×

Bounds on the number of complete subgraphs. (English) Zbl 0817.05035

Summary: Let \(G\) be a graph with a clique number \(w\). For \(1\leq j\leq w\), let \(k_ j\) be the number of complete subgraphs on \(j\) nodes. We show that \(k_{j+1} \leq(\begin{smallmatrix} w\\ j+1\end{smallmatrix})(k_ j/(\begin{smallmatrix} w\\ j\end{smallmatrix}))^{(j+ 1)/j}\). This is exact for complete balanced \(w\)-partite graphs and gives Turán’s theorem when \(j= 1\). A corollary is \[ w\geq {8k^ 3_ 2- 9k^ 2_ 3+ 3k_ 3 \sqrt{16k^ 3_ 2+ 9k^ 2_ 3}\over 4k^ 3_ 2- 18k^ 2_ 3}. \] This new bound on the clique number supersedes an earlier bound from Turán’s theorem.

MSC:

05C35 Extremal problems in graph theory
Full Text: DOI

References:

[1] Alavi, Y.; Malde, P. J.; Schwenk, A. J.; Erdős, P., The vertex independence sequence of a graph is not constrained, Congr. Numer., 58, 15-24 (1987) · Zbl 0679.05061
[2] Bollobás, B., Extremal Graph Theory (1978), Academic Press: Academic Press New York · Zbl 0419.05031
[3] Erdős, P., In the number of complete subgraphs and circuits contained in a graph, Časopis Pěst. Mat., 94, 290-296 (1969) · Zbl 0177.52502
[4] Fisher, D. C., The number of triangles in a \(K_4\)-free graph, Discrete Math., 69, 203-205 (1988) · Zbl 0659.05056
[5] Fisher, D. C., Lower bounds on the number of triangles in a graph, J. Graph Theory, 13, 505-512 (1989) · Zbl 0673.05046
[6] Fisher, D. C.; Ryan, J., Conjectures on the number of complete subgraphs, Congr. Numer., 70, 207-210 (1990) · Zbl 0701.05026
[7] Nordhaus, E. A.; Stewart, B. M., Triangles in ordinary graphs, Canad. J. Math., 15, 33-41 (1963) · Zbl 0115.17403
[8] Sauer, N., A. generalization of a theorem of Turán, J. Combin. Theory Ser. B, 12, 109-112 (1973) · Zbl 0216.02503
[9] Turán, P., On the theory of graphs, Colloq. Math., 3, 19-30 (1954) · Zbl 0055.17004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.