×

The formula for Turán number of spanning linear forests. (English) Zbl 1441.05116

Summary: Let \(\mathcal{F}\) be a family of graphs. The Turán number \(\operatorname{ex}( n ; \mathcal{F} )\) is defined to be the maximum number of edges in a graph of order \(n\) that is \(\mathcal{F} \)-free. P. Erdős and T. Gallai [Acta Math. Acad. Sci. Hung. 10, 337–356 (1959; Zbl 0090.39401)] determined the Turán number of \(M_{k + 1} \) (a matching of size \(k + 1)\) as follows: \[ \operatorname{ex}( n ; M_{k + 1} ) = \max \left\{ \binom{ 2 k + 1}{ 2}, \binom{ n}{ 2} - \binom{ n - k}{ 2}\right\}.\] Since then, there has been a lot of research on Turán number of linear forests. A linear forest is a graph whose connected components are all paths or isolated vertices. Let \(\mathcal{L}_{n , k}\) be the family of all linear forests of order \(n\) with \(k\) edges. In this paper, we prove that \[\operatorname{ex} ( n ; \mathcal{L}_{n , k} ) = \max \left\{ \binom{ k}{ 2}, \binom{ n }{2} - \binom{ n - \left\lfloor \frac{ k - 1}{ 2}\right\rfloor}{ 2} + c\right\},\] where \(c = 0\) if \(k\) is odd and \(c = 1\) otherwise. This determines the maximum number of edges in a non-Hamiltonian graph with given Hamiltonian completion number and also solves two open problems in [J. Wang and W. Yang, Discrete Appl. Math. 254, 291–294 (2019; Zbl 1404.05091)] as special cases. Moreover, we show that our main theorem implies Erdős-Gallai theorem and also gives a short new proof for it by the closure and counting techniques. Finally, we generalize our theorem to a conjecture which implies the famous Erdős matching conjecture.

MSC:

05C30 Enumeration in graph theory
05C35 Extremal problems in graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C75 Structural characterization of families of graphs

References:

[1] Akiyama, J.; Frankl, P., On the size of graphs with complete-factors, J. Graph Theory, 9, 197-201 (1985) · Zbl 0593.05042
[2] Bondy, J. A.; Chvátal, V., A method in graph theory, Discrete Math., 15, 111-135 (1976) · Zbl 0331.05138
[3] Bushaw, N.; Kettle, N., Turán numbers of multiple paths and equibipartite forests, Combin. Probab. Comput., 20, 837-853 (2011) · Zbl 1234.05128
[4] Erdős, P.; Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar, 10, 3-4, 337-356 (1959) · Zbl 0090.39401
[5] Erdős, P.; Ko, C.; Rado, R., Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser., 12, 2, 313-320 (1961) · Zbl 0100.01902
[6] Frankl, P., Proof of the Erdős matching conjecture in a new range, Israel J. Math., 222, 1, 421-430 (2017) · Zbl 1376.05122
[7] Goodman, S. E.; Hedetniemi, S. T., On the Hamiltoinaian completion problem, Graphs Combin., 262-272 (1974) · Zbl 0297.05134
[8] Goodman, S. E.; Hedetniemi, S. T.; Slater, P. J., Advances on the Hamiltonian completion problem, J. ACM, 22, 3, 544-555 (2012)
[9] Gorgol, I., Turán numbers for disjoint copies of graphs, Graphs Combin., 27, 661-667 (2011) · Zbl 1234.05129
[10] Hu, Z.; Tian, F.; Wei, B., Long cycles through a linear forest, J. Combin. Theory Ser. B, 82, 1, 67-80 (2001) · Zbl 1026.05065
[11] Keevash, P., Hypergraph Turán problems, Surv. Combin., 392, 83-140 (2011) · Zbl 1244.05159
[12] Li, B.; Broersma, H. J.; Zhang, S., Conditions for graphs to be path partition optimal, Discrete Math., 341, 1350-1358 (2018) · Zbl 1383.05187
[13] Li, B.; Ning, B., Spectral analogues of Erdős’ and Moon-Moser’s theorems on Hamilton cycles, Linear Multilinear Algebra, 64, 11, 2252-2269 (2016) · Zbl 1352.05105
[14] Li, B.; Ning, B.; Peng, X., Extremal problems on the hamiltonicity of claw-free graphs, Discrete Math., 341, 10, 2774-2788 (2018) · Zbl 1393.05173
[15] Lidicky, B.; Liu, H.; Palmer, C., On the Turán number of forests, Electron. J. Combin., 20, 2 (2013), #P62 · Zbl 1298.05071
[16] Ore, O., Arc coverings of graphs, Ann. Mat. Pura Appl., 55, 4, 315-321 (1961) · Zbl 0103.39702
[17] Ryjáček, Z., On a closure concept in claw-free graphs, J. Combin. Theory Ser. B (2), 70, 217-224 (1997) · Zbl 0872.05032
[18] Ryjáček, Z.; Vrána, P.; Wang, S., Closure for \(K_{1 , 4} , K_{1 , 4} + e\)-free graphs, J. Combin. Theory Ser. B, 134, 239-263 (2019) · Zbl 1402.05130
[19] Sidorenko, A., What we know and what we do not know about Turán numbers, Graphs Combin., 11, 179-199 (1995) · Zbl 0839.05050
[20] Turán, P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 48, 436-452 (1941), (in Hungarian) · Zbl 0026.26903
[21] Wang, J.; Yang, W., The Turán number for spanning linear forests, Discrete Appl. Math., 254, 291-294 (2019) · Zbl 1404.05091
[22] Yuan, L.; Zhang, X., The Turán number of disjoint copies of paths, Discrete Math., 340, 2, 132-139 (2017) · Zbl 1351.05122
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.