Article in press
Authors:
Title:
The Turán number of three disjoint paths
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-12-26 , Revised: 2023-07-01 , Accepted: 2023-07-02 , Available online: 2023-07-27 , https://doi.org/10.7151/dmgt.2507
Abstract:
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 $\bigcup_{i=1}^{m}P_{k_{i}}$ denote the
disjoint union of $P_{k_i}$ for $1\le i\le m$; in particular, write
$\bigcup_{i=1}^{m}P_{k_{i}}=mP_k$ if $k_i=k$ for all $1\le i\le m$. Yuan and
Zhang determined ex$(n,\bigcup_{i=1}^{m}P_{k_{i}})$ for all integers $n$
if at most one of $k_{1},\dots,k_{m}$ is odd. Much less is known for all
integers $n$ if at least two of $k_{1},\dots,k_{m}$ are odd. Partial results
such as ex$(n,mP_3)$, ex$(n,P_{3}\cup P_{2\ell+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}\cup P_{2\ell+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
References:
- 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 - H. Bielak and S. Kieliszek, The Turán number of the graph $2P_5$, Discuss. Math. Graph Theory 36 (2016) 683–694.
https://doi.org/10.7151/dmgt.1883 - 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 - 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 - 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 - 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 - 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 - L. Feng and Y. Hu, The Turán number of the graph $3P_{5}$, Filomat 34 (2020) 3395–3410.
https://doi.org/10.2298/FIL2010395F - 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 - 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 - 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 - 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 - G.N. Kopylov, On maximal paths and cycles in a graph, Dokl. Akad. Nauk SSSR 234 (1977) 19–21.
- Y. Lan, Z. Qin and Y.-T. Shi, The Turán number of $2P_{7}$, Discuss. Math. Graph Theory 39 (2019) 805–814.
https://doi.org/10.7151/dmgt.2111 - 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 - 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 - 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 - 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
Close