Article in volume
Authors:
Title:
The Turán number for $4\cdot S_\ell$
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1119-1128
Received: 2019-10-25 , Revised: 2020-05-09 , Accepted: 2020-05-09 , Available online: 2020-06-17 , https://doi.org/10.7151/dmgt.2338
Abstract:
The Turán number of a graph $H$, denoted by $ex{(n,H)}$,
is the maximum number of edges of an $n$-vertex simple graph having
no $H$ as a subgraph. Let $S_\ell$ denote the star on $\ell+1$
vertices, and let $k\cdot S_\ell$ denote $k$ disjoint copies of
$S_\ell$. Erdős and Gallai determined the value $ex(n,k\cdot S_1)$ for all
positive integers $k$ and $n$. Yuan and Zhang determined the value
$ex(n,k\cdot S_2)$ and characterized all extremal graphs for all positive
integers $k$ and $n$. Recently, Lan et al. determined the value
$ex(n,2\cdot S_3)$ for all positive integers $n$, and Li and Yin determined
the values $ex(n,k\cdot S_\ell)$ for $k=2,3$ and all positive integers $\ell$
and $n$. In this paper, we further determine the value $ex(n,4\cdot S_\ell)$
for all positive integers $\ell$ and almost all $n$, improving one of the
results of Lidický et al.
Keywords:
Turán number, disjoint copies, $k\cdot S_\ell$
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, 1976).
- 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 - 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 - Y.X. Lan, T. Li, Y.T. Shi and J.H. Tu, The Turán number of star forests, Appl. Math. Comput. 348 (2019) 270–274.
https://doi.org/10.1016/j.amc.2018.12.004 - Y.X. Lan, H. Liu, Z.M. Qin and Y.T. Shi, Degree powers in graphs with a forbidden forest, Discrete Math. 342 (2019) 821–835.
https://doi.org/10.1016/j.disc.2018.11.013 - S.-S. Li and J.-H. Yin, Two results about the Turán number of star forests, Discrete Math. 343 (2020) 111702.
https://doi.org/10.1016/j.disc.2019.111702 - B. Lidický, H. Liu and C. Palmer, On the Turán number of forests, Electron. J. Combin. 20 (2013) #P62.
https://doi.org/10.37236/3142 - M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs, P. Erdős, G. Katona (Ed(s)), (Academic Press, New York 1968) 279–319.
- P. Turán, An extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436–452, in Hungarian.
- J.H. Yin and Y. Rao, Turán number for $p\cdot Sr$, J. Combin. Math. Combin. Comput. 97 (2016) 241–245.
- 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
Close