Geodesic
The Turań Number of 2P7
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 805-814.

Voir la notice de l'article provenant de la source Library of Science

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 (mod 6) and 0 ≤ r lt; 6.
Keywords: Turán number, extremal graphs, 2 P 7 
@article{DMGT_2019_39_4_a2,
     author = {Lan, Yongxin and Qin, Zhongmei and Shi, Yongtang},
     title = {The {Tura\'n} {Number} of {2P\protect\textsubscript{7}}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {805--814},
     publisher = {mathdoc},
     volume = {39},
     number = {4},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a2/}
}
TY  - JOUR
AU  - Lan, Yongxin
AU  - Qin, Zhongmei
AU  - Shi, Yongtang
TI  - The Turań Number of 2P7
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 805
EP  - 814
VL  - 39
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a2/
LA  - en
ID  - DMGT_2019_39_4_a2
ER  - 
%0 Journal Article
%A Lan, Yongxin
%A Qin, Zhongmei
%A Shi, Yongtang
%T The Turań Number of 2P7
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 805-814
%V 39
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a2/
%G en
%F DMGT_2019_39_4_a2
Lan, Yongxin; Qin, Zhongmei; Shi, Yongtang. The Turań Number of 2P7. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 805-814. http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a2/

[1] P.N. Balister, E. Győri, J. Lehel and R.H. Schelp, Connected graphs without long paths, Discrete Math. 308 (2008) 4487–4494. doi:10.1016/j.disc.2007.08.047

[2] H. Bielak and S. Kieliszek, The Turán number of the graph 2P5, Discuss. Math. Graph Theory 36 (2016) 683–694. doi:10.7151/dmgt.1883

[3] B. Bollobás, Modern Graph Theory (Springer, 2013).

[4] N. Bushaw and N. Kettle, Turán numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20 (2011) 837–853. doi:10.1017/S0963548311000460

[5] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar 10 (1959) 337–356. doi:10.1007/BF02024498

[6] P. Erdős, Über ein Extremalproblem in der Graphentheorie, Arch. Math. (Basel) 13 (1962) 222–227, in German. doi:10.1007/BF01650069

[7] R.J. Faudree and R.H. Schelp, Path Ramsey numbers in multicolourings, J. Combin. Theory Ser. B 19 (1975) 150–160. doi:10.1016/0095-8956(75)90080-5

[8] G.N. Kopylov, Maximal paths and cycles in a graph, Dokl. Akad. Nauk SSSR 234 (1977) 19–21. (English translation in Soviet Math. Dokl. 18 (1977) 593–596.)

[9] Y. Lan, Y. Shi and Z.-X. Song, Planar Turán numbers for Theta graphs and paths of small order, arXiv:1711.01614v1.

[10] B. Lidický, H. Liu and C. Palmer, On the Turán number of forests, Electron. J. Combin. 20 (2013) #P62.

[11] J.W. Moon, On independent complete subgraphs in a graph, Canad. J. Math. 20 (1968) 95–102. doi:10.4153/CJM-1968-012-x

[12] M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs (Academic Press, 1968) 279–319.

[13] P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941) 436–452, in Hungarian.

[14] P. Turán, On the theory of graphs, Colloq. Math. 3 (1954) 19–30. doi:10.4064/cm-3-1-19-30

[15] L. Yuan and X. Zhang, Turán numbers for disjoint paths, arXiv: 1611.00981v1.

[16] L. Yuan and X. Zhang, The Turán number of disjoint copies of paths, Discrete Math. 340 (2017) 132–139. doi:10.1016/j.disc.2016.08.004