Geodesic
The Turán number of spanning star forests
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 303-312 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Let ℱ be a family of graphs. The Turán number of ℱ, denoted by ex(n, ℱ), is the maximum number of edges in a graph with n vertices which does not contain any subgraph isomorphic to some graph in ℱ. 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 𝒮_n, k be the set of all star forests with n vertices and k edges. We prove that when 1≤ k≤ n-1, ex(n,𝒮_n, k)= ⌊k^2-1/2⌋.
Keywords: spanning Turán problem, star forests, Loebl-Komlós-Sós type problems 
@article{DMGT_2023_43_2_a0,
     author = {Zhang, Lin-Peng and Wang, Ligong and Zhou, Jiale},
     title = {The {Tur\'an} number of spanning star forests},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {303--312},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a0/}
}
TY  - JOUR
AU  - Zhang, Lin-Peng
AU  - Wang, Ligong
AU  - Zhou, Jiale
TI  - The Turán number of spanning star forests
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 303
EP  - 312
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a0/
LA  - en
ID  - DMGT_2023_43_2_a0
ER  - 
%0 Journal Article
%A Zhang, Lin-Peng
%A Wang, Ligong
%A Zhou, Jiale
%T The Turán number of spanning star forests
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 303-312
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a0/
%G en
%F DMGT_2023_43_2_a0
Zhang, Lin-Peng; Wang, Ligong; Zhou, Jiale. The Turán number of spanning star forests. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 303-312. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a0/

[1] B. Bollobás, Modern Graph Theory (Springer, New York, 2013). https://doi.org/10.1007/978-1-4612-0619-4

[2] P. Erdős, Z. Füredi, M. Loebl and V.T. Sós, Discrepancy of trees, Studia Sci. Math. Hungar. 30 (1995) 47–57.

[3] 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

[4] 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

[5] 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

[6] 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

[7] 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

[8] 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

[9] 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

[10] 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

[11] 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

[12] 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

[13] 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

[14] 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.

[15] P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941) 436–452, in Hungarian.

[16] P. Turán, On the theory of graphs, Colloq. Math. 3 (1954) 19–30. https://doi.org/10.4064/cm-3-1-19-30

[17] 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

[18] J.-H. Yin and Y. Rao, Turán number for p\cdot Sr, J. Combin. Math. Combin. Comput. 97 (2016) 241–245.