Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-12T06:28:24.362Z Has data issue: false hasContentIssue false
  • English
  • Français

Extensions of the Erdős–Gallai theorem and Luo’s theorem

Part of:Graph theory

Published online by Cambridge University Press:  08 October 2019

Bo Ning and
Xing Peng
Bo Ning
Affiliation:
Center for Applied Mathematics, Tianjin University, Tianjin, 300062, P. R.China Emails: bo.ning@tju.edu.cn; x2peng@tju.edu.cn
Xing Peng*
Affiliation:
Center for Applied Mathematics, Tianjin University, Tianjin, 300062, P. R.China Emails: bo.ning@tju.edu.cn; x2peng@tju.edu.cn
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The famous Erdős–Gallai theorem on the Turán number of paths states that every graph with n vertices and m edges contains a path with at least (2m)/n edges. In this note, we first establish a simple but novel extension of the Erdős–Gallai theorem by proving that every graph G contains a path with at least

$${{(s + 1){N_{s + 1}}(G)} \over {{N_s}(G)}} + s - 1$$
edges, where Nj(G) denotes the number of j-cliques in G for 1≤ j ≤ ω(G). We also construct a family of graphs which shows our extension improves the estimate given by the Erdős–Gallai theorem. Among applications, we show, for example, that the main results of [20], which are on the maximum possible number of s-cliques in an n-vertex graph without a path with ℓ vertices (and without cycles of length at least c), can be easily deduced from this extension. Indeed, to prove these results, Luo [20] generalized a classical theorem of Kopylov and established a tight upper bound on the number of s-cliques in an n-vertex 2-connected graph with circumference less than c. We prove a similar result for an n-vertex 2-connected graph with circumference less than c and large minimum degree. We conclude this paper with an application of our results to a problem from spectral extremal graph theory on consecutive lengths of cycles in graphs.

MSC classification

Primary:05C35: Extremal problems05C38: Paths and cycles

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 1 , January 2020, pp. 128 - 136
Copyright
© Cambridge University Press 2019 

Footnotes

†

Supported by the NSFC grants (11601379, 11771141, 11971346) and the Seed Foundation of Tianjin University (2018XRG-0025).

‡

Supported by the NSFC grant (11601380) and the Seed Foundation of Tianjin University (2017XRX-0011)

References

Alon, N. and Shikhelman, C. (2016) Many T-copies in H-free graphs. J. Combin. Theory Ser. B 121 146–172.CrossRefGoogle Scholar
Bollobás, B. (1978) Extremal Graph Theory, Cambridge University Press.Google Scholar
Bollobás, B. and Győri, E. (2008) Pentagons vs. triangles. Discrete Math . 308 4332–4336.CrossRefGoogle Scholar
Bondy, J. A. (1971) Large cycles in graphs. Discrete Math . 1 121–132.CrossRefGoogle Scholar
Bondy, J. A. and Fan, G. (1991) Cycles in weighted graphs. Combinatorica 11 191–205.CrossRefGoogle Scholar
Caccetta, L. and Vijayan, K. (1991) Long cycles in subgraphs with prescribed minimum degree. Discrete Math . 97 69–81.CrossRefGoogle Scholar
Erdős, P. (1962) Remarks on a paper of Pósa. Magya Tud. Akad. Mat. Kutató Int. Közl. 7 227–229.Google Scholar
Erdős, P. (1962) On the number of complete subgraphs contained in certain graphs. Magya Tud. Akad. Mat. Kutató Int. Közl. 7 459–474.Google Scholar
Erdős, P. and Gallai, T. (1959) On maximal paths and circuits of graphs. Acta Math. Hungar . 10 337–356.CrossRefGoogle Scholar
Ergemlidze, B., Győri, E., Methuku, A. and Salia, N. (2019) A note on the maximum number of triangles in a -free graph. J. Graph Theory 90 227–230.CrossRefGoogle Scholar
Fan, G. (1990) Long cycles and the codiameter of a graph, I. J. Combin. Theory Ser. B 49 151–180.CrossRefGoogle Scholar
Fan, G., Lv, X. and Wang, P. (2004) Cycles in 2-connected graphs. J. Combin. Theory Ser. B 92 379–394.CrossRefGoogle Scholar
Faudree, R. J. and Schelp, R. H. (1975) Path Ramsey numbers in multicolorings. J. Combin. Theory Ser. B 19 150–160.CrossRefGoogle Scholar
Füredi, Z. and Simonovits, M. (2013) The history of degenerate (bipartite) extremal graph problems. In Erdős centennial (L. Lovász et al., eds), Vol 25 of Bolyai Mathematical Society Studies, Springer, 169–264.CrossRefGoogle Scholar
Grzesik, A. (2012) On the maximum number of five-cycles in a triangle-free graph. J. Combin. Theory Ser. B, 102 1061–1066.CrossRefGoogle Scholar
Győri, E., Methuku, A., Salia, N., Tompkins, C. and Vizer, M. (2018) On the maximum size of connected hypergraphs without a path of given length. Discrete Math . 341 2602–2605.CrossRefGoogle Scholar
Hatami, H., Hladký, J., Králą, D., Norine, S. and Razborov, A. (2013) On the number of pentagons in triangle-free graphs. J. Combin. Theory Ser. A 120 722–732.CrossRefGoogle Scholar
Kopylov, G. N. (1977) Maximal paths and cycles in a graph. Dokl. Akad. Nauk SSSR 234 19–21. English translation: Soviet Math. Dokl. 18 (1977) 593–596.Google Scholar
Lewin, M. (1975) On maximal circuits in directed graphs. J. Combin. Theory Ser. B 18 175–179.CrossRefGoogle Scholar
Luo, R. (2017) The maximum number of cliques in graphs without long cycles. J. Combin. Theory Ser. B 128 219–226.CrossRefGoogle Scholar
Nikiforov, V. (2008) A spectral condition for odd cycles in graphs. Linear Algebra Appl . 428 1492–1498.CrossRefGoogle Scholar
Woodall, D. R. (1972) Sufficient conditions for circuits in graphs. Proc. London Math. Soc. 24 739–755.CrossRefGoogle Scholar
Woodall, D. R. (1976) Maximal circuits of graphs I. Acta Math. Acad. Sci. Hungar. 28 77–80.CrossRefGoogle Scholar