Authors:
Y. Lan, Z. Qin, Y.T. Shi
Title:
The Turán number of 2P7
Source:
Discussiones Mathematicae Graph Theory
Received 04.03.2017, Revised 22.11.2017, Accepted 22.11.2017, doi: 10.7151/dmgt.2111

Abstract:
The Turán number of a graph H, denoted by ex(n,H), is the maximum number of edges in any graph on n vertices which does not contain H as a subgraph. Let Pk denote the path on k vertices and let mPk denote m disjoint copies of Pk. Bushaw and Kettle [ Turán numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20 (2011) 837--853] determined the exact value of ex(n,kP) for large values of n. Yuan and Zhang [ The Turán number of disjoint copies of paths, Discrete Math. 340 (2017) 132--139] completely determined the value of ex(n,kP3) for all n, and also determined ex(n,Fm), where Fm is the disjoint union of m paths containing at most one odd path. They also determined the exact value of ex(n,P3∪ P2{ℓ}+1) for n≥ 2{ℓ}+4. Recently, Bielak and Kieliszek [ The Turán number of the graph 2P5, Discuss. Math. Graph Theory 36 (2016) 683--694], Yuan and Zhang [ Turán numbers for disjoint paths, arXiv:1611.00981v1] independently determined the exact value of ex(n,2P5). In this paper, we show that ex(n,2P7)=\max{[n,14,7],5n-14} for all n ≥ 14, where [n,14,7]=(5n+91+r(r-6))/2, n-13≡ r\,(\text{mod }6) and 0≤ r< 6.
Keywords:
Turán number, extremal graphs, 2P7

Links:
PDF