Geodesic
The Turán number of three disjoint paths
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1513-1537

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

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},
     publisher = {mathdoc},
     volume = {44},
     number = {4},
     year = {2024},
     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
PB  - mathdoc
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
%I mathdoc
%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/