Geodesic
The Turán number of three disjoint paths
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1513-1537 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

The Turán number of a graph H, ex(n,H), is the maximum number of edges in an n-vertex graph that does not contain H as a subgraph. Let P_k denote the path on k vertices and let ⋃_i=1^mP_k_i denote the disjoint union of P_k_i for 1≤ i≤ m; in particular, write ⋃_i=1^mP_k_i=mP_k if k_i=k for all 1≤ i≤ m. Yuan and Zhang determined ex(n,⋃_i=1^mP_k_i) for all integers n if at most one of k_1,...,k_m is odd. Much less is known for all integers n if at least two of k_1,...,k_m are odd. Partial results such as ex(n,mP_3), ex(n,P_3∪ P_2ℓ+1), (n,2P_5), ex(n,2P_7) and ex(n,3P_5) have been established by several researchers. In this paper, we develop new functions and determine ex(n,3P_7) and ex(n,2P_3∪ P_2ℓ+1) for all integers n. We also characterize all the extremal graphs. Both results contribute to a conjecture of Yuan and Zhang.
Keywords: Turán number, disjoint paths, extremal graph 
@article{DMGT_2024_44_4_a14,
     author = {Deng, Jinghua and Hou, Jianfeng and Zeng, Qinghou},
     title = {The {Tur\'an} number of three disjoint paths},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1513--1537},
     year = {2024},
     volume = {44},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a14/}
}
TY  - JOUR
AU  - Deng, Jinghua
AU  - Hou, Jianfeng
AU  - Zeng, Qinghou
TI  - The Turán number of three disjoint paths
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1513
EP  - 1537
VL  - 44
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a14/
LA  - en
ID  - DMGT_2024_44_4_a14
ER  - 
%0 Journal Article
%A Deng, Jinghua
%A Hou, Jianfeng
%A Zeng, Qinghou
%T The Turán number of three disjoint paths
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1513-1537
%V 44
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a14/
%G en
%F DMGT_2024_44_4_a14
Deng, Jinghua; Hou, Jianfeng; Zeng, Qinghou. The Turán number of three disjoint paths. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1513-1537. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a14/

[1] P.N. Balister, E. Győri, J. Lehel and R.H. Schelp, Connected graphs without long paths, Discrete Math. 308 (2008) 4487–4494. https://doi.org/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. https://doi.org/10.7151/dmgt.1883

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

[4] N. Bushaw and N. Kettle, Turán numbers for forests of paths in hypergraphs, SIAM J. Discrete Math. 28 (2014) 711–721. https://doi.org/10.1137/130913833

[5] V. Campos and R. Lopes, A proof for a conjecture of Gorgol, Discrete Appl. Math. 245 (2018) 202–207. https://doi.org/10.1016/j.dam.2017.04.012

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

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

[8] L. Feng and Y. Hu, The Turán number of the graph 3P5, Filomat 34 (2020) 3395–3410. https://doi.org/10.2298/FIL2010395F

[9] Z. Füredi and T. Jiang, Hypergraph Turán numbers of linear cycles, J. Combin. Theory Ser. A 123 (2014) 252–270. https://doi.org/10.1016/j.jcta.2013.12.009

[10] Z. Füredi, T. Jiang and R. Seiver, Exact solution of the hypergraph Turán problem for k-uniform linear paths, Combinatorica 34 (2014) 299–322. https://doi.org/10.1007/s00493-014-2838-4

[11] I. Gorgol, Turán numbers for disjoint copies of graphs, Graphs Combin. 27 (2011) 661–667. https://doi.org/10.1007/s00373-010-0999-5

[12] R. Gu, X.-L. Li and Y.-T. Shi, Hypergraph Turán numbers of vertex disjoint cycles, Acta Math. Appl. Sin. Engl. Ser. 38 (2022) 229–234. https://doi.org/10.1007/s10255-022-1056-x

[13] G.N. Kopylov, On maximal paths and cycles in a graph, Dokl. Akad. Nauk SSSR 234 (1977) 19–21.

[14] Y. Lan, Z. Qin and Y.-T. Shi, The Turán number of 2P7, Discuss. Math. Graph Theory 39 (2019) 805–814. https://doi.org/10.7151/dmgt.2111

[15] H. Liu, B. Lidický and C. Palmer, On the Turán number of forests, Electron. J. Combin. 20(2) (2013) #P62. https://doi.org/10.37236/3142

[16] J. Wang and W. Yang, The Turán number for spanning linear forests, Discrete Appl. Math. 254 (2019) 291–294. https://doi.org/10.1016/j.dam.2018.07.014

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

[18] L.-T. Yuan and X.-D. Zhang, Turán number for disjoint paths, J. Graph Theory 98 (2021) 499–524. https://doi.org/10.1002/jgt.22710