Hostname: page-component-55f67697df-xq6d9 Total loading time: 0 Render date: 2025-05-10T01:48:23.823Z Has data issue: false hasContentIssue false

HOW MANY TRIANGLES CAN A GRAPH HAVE?

Published online by Cambridge University Press:  14 November 2024

TEERADEJ KITTIPASSORN*
Affiliation:
Department of Mathematics and Computer Science, Faculty of Science, Chulalongkorn University, Bangkok 10330, Thailand
KAMIL POPIELARZ
Affiliation:
Zurich, Switzerland e-mail: [email protected]

Abstract

We investigate the set $T_{n}$ of the possible number of triangles in a graph on n vertices. The first main result says that every natural number less than $\binom {n}{3} - (\sqrt {2}+o(1) )n^{3/2} $ belongs to $T_{n}$. On the other hand, we show that there is a number $m = \binom {n}{3}-( \sqrt {2} +o(1))n^{3/2}$ that is not a member of $T_{n}$. In addition, we prove that there are two interlacing sequences $\binom {n}{3} - ( \sqrt {2} + o(1) )n^{3/2} = c_{1} \le d_{1} \le c_{2} \le d_{2} \le \cdots \le c_{s} \le d_{s} = \binom {n}{3}$ with $| c_{t} - d_{t}| = n-2-\binom {s - t +1}{2}$ such that $( c_{t}, d_{t} ) \cap T_{n} = \emptyset $ for all t. Moreover, we obtain a generalisation of these results for the set of the possible number of copies of a connected graph H in a graph on n vertices.

MSC classification

Type
Research Article
Copyright
© The Author(s), 2024. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

Footnotes

The first author was partially supported by Office of the Permanent Secretary, Ministry of Higher Education, Science, Research and Innovation grant RGNS 63-016.

References

Alon, N., ‘On the number of subgraphs of prescribed type of graphs with a given number of edges’, Israel J. Math. 38(1–2) (1981), 116130.CrossRefGoogle Scholar
Balister, P. and Dogan, A., ‘On the edge spectrum of saturated graphs for paths and stars’, J. Graph Theory 89(4) (2018), 364385.CrossRefGoogle Scholar
Cutler, J. and Radcliffe, A. J., ‘The maximum number of complete subgraphs in a graph with given maximum degree’, J. Combin. Theory Ser. B 104 (2014), 6071.CrossRefGoogle Scholar
Erdős, P., ‘On the number of complete subgraphs contained in certain graphs’, Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7 (1962), 459464.Google Scholar
Erdős, P., ‘On a theorem of Rademacher–Turán’, Illinois J. Math. 6(1) (1962), 122127.CrossRefGoogle Scholar
Erdős, P., ‘On the number of triangles contained in certain graphs’, Canad. Math. Bull. 7 (1964), 5356.CrossRefGoogle Scholar
Erdős, P., ‘On the number of complete subgraphs and circuits contained in graphs’, Cas. Pestováni Mat. 94 (1969), 290296.Google Scholar
Füredi, Z., ‘Graphs with maximum number of star-forests’, Studia Sci. Math. Hungar. 27 (1992), 403407.Google Scholar
Kittipassorn, T. and Mészáros, G., ‘Frustrated triangles’, Discrete Math. 338(12) (2015), 23632373.CrossRefGoogle Scholar
Larman, D. G., ‘On the number of complete subgraphs and circuits in a graph’, Proc. Roy. Soc. Edinburgh Sect. A 308(1494) (1969), 327342.Google Scholar
Lovász, L. and Simonovits, M., ‘On the number of complete subgraphs of a graph II’, in: Studies in Pure Mathematics (eds. Erdős, P., Alpár, L., Halász, G. and Sárközy, A.) (Springer, Basel, 1983), 459495; to the memory of Paul Turán.CrossRefGoogle Scholar
Nikiforov, V., ‘The number of cliques in graphs of given order and size’, Trans. Amer. Math. Soc. 363 (2011), 15991618.CrossRefGoogle Scholar
Nordhaus, E. A. and Stewart, B. M, ‘Triangles in an ordinary graph’, Canad. J. Math. 15 (1963), 3341.CrossRefGoogle Scholar