zbMATH — the first resource for mathematics

Lower bounds on the number of triangles in a graph. (English) Zbl 0673.05046
Summary: For a simple graph G, let \(f(z)\equiv 1-c_ 1z+c_ 2z^ 2-c_ 3z^ 3+..\). where \(c_ k\) is the number of complete subgraphs on k nodes in G. Let r(G) be the reciprocal of the smallest real root of f(z). Let \(\lambda(\bar G)\) be the spectral radius of the complement of G. We show \(r(G)\geq \lambda (\bar G)+1.\) This is used to show that if \(c^ 2_ 1/4\leq c_ 2\leq c^ 2_ 1/3\), then a lower bound on the number of triangles in G is \(c_ 3\geq [9c_ 2c_ 1-2c^ 3_ 1-2(c^ 2_ 1- 3c_ 2)^{3/2}]/27.\) This improves a bound of Bollobás and is asymptotically sharp.
Also, this paper shows that \(c_ 3\leq c_ 2(\sqrt{8c_ 2+1}-3)/6\) (a corollary of a result from Erdős and Hanini) and the average number of triangles in a graph with \(c_ 1\) nodes and \(c_ 2\) edges is \(E(c_ 3)=(4/3)(c^ 2_ 2-3c_ 2+2)c_ 2/(c^ 3_ 1-5c_ 1-4).\) These are graphically compared to the best known lower bounds.

05C35 Extremal problems in graph theory
Full Text: DOI
[1] Extremal Graph Theory. Academic Press, (1978). · Zbl 0419.05031
[2] Erdös, Pub. Math. Institute Hung. Acad. Sci. 7 pp 459– (1962)
[3] Fisher, Discrete Math. 69 pp 203– (1988)
[4] Fisher, Am. Math. Month.
[5] Fisher, Discrete Math.
[6] and , On complete subgraphs of a graph II. Studies Pure Math. (1983) 459–496.
[7] Nikiforov, C.R. Acad. Bulg. Sci. 34 pp 969– (1981)
[8] Nordhaus, Can. J. Math. 15 pp 33– (1963) · Zbl 0115.17403 · doi:10.4153/CJM-1963-004-7
[9] Graphical Evolution. Wiley, New York (1985).
[10] and , On the eigenvalues of a graph. Selected Topics in Graph Theory. Academic Press, San Francisco (1978) 307–337.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.