Article in volume
Authors:
Title:
The Turán number of spanning star forests
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 303-312
Received: 2020-01-22 , Revised: 2020-09-26 , Accepted: 2020-09-26 , Available online: 2020-10-20 , https://doi.org/10.7151/dmgt.2368
Abstract:
Let $\mathcal{F}$ be a family of graphs. The Turán number of $\mathcal{F}$,
denoted by $ex(n, \mathcal{F})$, is the maximum number of edges in a graph with
$n$ vertices which does not contain any subgraph isomorphic to some graph in
$\mathcal{F}$. A star forest is a forest whose connected components are all
stars and isolated vertices. Motivated by the results of Wang, Yang and Ning
about the spanning Turán number of linear forests [J. Wang and W. Yang,
The Turán number for spanning linear forests, Discrete Appl. Math. 254
(2019) 291–294; B. Ning and J. Wang, The formula for Turán number of
spanning linear forests, Discrete Math. 343 (2020) 111924]. In this
paper, let $\mathcal{S}_{n, k}$ be the set of all star forests with $n$ vertices
and $k$ edges. We prove that when $1\le k\le n-1$, $ex(n,\mathcal{S}_{n, k})=
\left\lfloor \frac{k^2-1}{2}\right\rfloor.$
Keywords:
spanning Turán problem, star forests, Loebl-Komlós-Sós type problems
References:
- B. Bollobás, Modern Graph Theory (Springer, New York, 2013).
https://doi.org/10.1007/978-1-4612-0619-4 - P. Erdős, Z. Füredi, M. Loebl and V.T. Sós, Discrepancy of trees, Studia Sci. Math. Hungar. 30 (1995) 47–57.
- P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hung. 10 (1959) 337–356.
https://doi.org/10.1007/BF02024498 - Z. Füredi and M. Simonovits, The history of degenerate $($bipartite$)$ extremal graph problems, in: Erdős Centennial, Bolyai Soc. Math. Stud. 25, (Springer, Berlin, Heidelberg 2013) 169–294.
https://doi.org/10.1007/978-3-642-39286-3_7 - 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 - J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture I: The sparse decomposition, SIAM J. Discrete Math. 31 (2017) 945–982.
https://doi.org/10.1137/140982842 - J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs, SIAM J. Discrete Math. 31 (2017) 983–1016.
https://doi.org/10.1137/140982854 - J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs, SIAM J. Discrete Math. 31 (2017) 1017–1071.
https://doi.org/10.1137/140982866 - J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result, SIAM J. Discrete Math. 31 (2017) 1072–1148.
https://doi.org/10.1137/140982878 - Y. Lan, T. Li, Y. Shi and J. 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 - 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 - B. Ning and J. Wang, The formula for Turán number of spanning linear forests, Discrete Math. 343 (2020) 111924.
https://doi.org/10.1016/j.disc.2020.111924 - M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs, P. Erdős and G. Katona (Ed(s)), (Academic Press, New York 1968) 279–319.
- P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941) 436–452, in Hungarian.
- P. Turán, On the theory of graphs, Colloq. Math. 3 (1954) 19–30.
https://doi.org/10.4064/cm-3-1-19-30 - 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 - J.-H. Yin and Y. Rao, Turán number for $p\cdot S_r$, J. Combin. Math. Combin. Comput. 97 (2016) 241–245.
Close