×

Maximising the number of cycles in graphs with forbidden subgraphs. (English) Zbl 1458.05114

Summary: Fix \(k\geq 2\) and let \(H\) be a graph with \(\chi(H)=k+1\) containing a critical edge. We show that for sufficiently large \(n\), the unique \(n\)-vertex \(H\)-free graph containing the maximum number of cycles is \(T_k(n)\). This resolves both a question and a conjecture of A. Arman et al. [Discrete Math. 339, No. 2, 699–711 (2016; Zbl 1327.05170)].

MSC:

05C30 Enumeration in graph theory
05C38 Paths and cycles
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Citations:

Zbl 1327.05170
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahrens, W., Ueber das Gleichungssystem einer Kirchhoff’schen galvanischen Stromverzweigung, Math. Ann., 49, 2, 311-324 (1897) · JFM 28.0770.01
[2] Alon, N.; Shikhelman, C., Many T copies in H-free graphs, J. Comb. Theory, Ser. B, 121, 146-172 (2016) · Zbl 1348.05100
[3] Arman, A., Maximum number of cycles in graphs and multigraphs (2018), Ph.D. thesis, The University of Manitoba
[4] Arman, A.; Gunderson, D. S.; Tsaturian, Sergei, Triangle-free graphs with the maximum number of cycles, Discrete Math., 339, 699-711 (2016) · Zbl 1327.05170
[5] Arman, A.; Tsaturian, A., The maximum number of cycles in a graph with fixed number of edges (February 2017)
[6] Bollobás, B., On complete subgraphs of different orders, Math. Proc. Camb. Philos. Soc., 79, 1, 19-24 (1976) · Zbl 0325.05117
[7] Bollobás, B., Extremal Graph Theory (1978), Academic Press: Academic Press London · Zbl 0419.05031
[8] Bollobás, B.; Győri, E., Pentagons vs. triangles, Discrete Math., 308, 19, 4332-4336 (2008) · Zbl 1152.05034
[9] Durocher, S.; Gunderson, D. S.; Li, P. C.; Skala, M., Cycle-maximal triangle-free graphs, Discrete Math., 338, 274-290 (2015) · Zbl 1303.05091
[10] Erdős, P., On the number of complete subgraphs contained in certain graphs, Magy. Tud. Akad. Mat. Kut. Intéz. Közl., 7, 459-464 (1962) · Zbl 0116.01202
[11] Erdős, P.; Simonovits, M., A limit theorem in graph theory, Studia Sci. Math. Hung., 1, 51-57 (1966) · Zbl 0178.27301
[12] Erdős, P.; Stone, A. H., On the structure of linear graphs, Bull. Am. Math. Soc., 52, 1087-1091 (1946) · Zbl 0063.01277
[13] Feller, W., Introduction to Probability Theory and Its Applications, Vol. I (1968), John Wiley & Sons: John Wiley & Sons New York · Zbl 0155.23101
[14] Grzesik, A., On the maximum number of five-cycles in a triangle-free graph, J. Comb. Theory, Ser. B, 102, 5, 1061-1066 (2012) · Zbl 1252.05093
[15] Grzesik, A.; Kielak, B., On the maximum number of odd cycles in graphs without smaller odd cycles (June 2018)
[16] Győri, E.; Li, H., The maximum number of triangles in \(C_{2 k + 1}\)-free graphs, Comb. Probab. Comput., 21, 1-2, 187-191 (2012) · Zbl 1238.05145
[17] Hatami, H.; Hladký, J.; Král’, D.; Norine, S.; Razborov, A., On the number of pentagons in triangle-free graphs, J. Comb. Theory, Ser. A, 120, 722-732 (2013) · Zbl 1259.05087
[18] Király, Z., Maximum number of cycles and Hamiltonian cycles in sparse graphs (2009), Tech. report
[19] Kirchhoff, G., Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird, Ann. Phys., 148, 12, 497-508 (1847)
[20] Morrison, N.; Scott, A., Maximising the number of induced cycles in a graph, J. Comb. Theory, Ser. B, 126, 24-61 (2017) · Zbl 1368.05081
[21] Roberts, A.; Scott, A., Stability results for graphs with a critical edge, Eur. J. Comb., 74, 27-38 (2018) · Zbl 1394.05035
[22] Simonovits, M., Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions, Discrete Math., 7, 349-376 (1974) · Zbl 0274.05113
[23] Turán, P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 48, 436-452 (1941) · Zbl 0026.26903
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.