1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

The Turán Number of Spanning Star Forests

Published Online: 24 Nov 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 01 Jun 2020
Accepted: 26 Sep 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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 ≤ kn − 1, ex(n, 𝒮n,k) = ex(n,𝒮n,k)=k2-12ex\left( {n,{\mathcal{S}_{n,k}}} \right) = \left\lfloor {{{{k_2} - 1} \over 2}} \right\rfloor.

Keywords

MSC 2010

[1] B. Bollobás, Modern Graph Theory (Springer, New York, 2013). doi:10.1007/978-1-4612-0619-410.1007/978-1-4612-0619-4Search in Google Scholar

[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.Search in Google Scholar

[3] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hung. 10 (1959) 337–356. doi:10.1007/BF0202449810.1007/BF02024498Search in Google Scholar

[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. doi:10.1007/978-3-642-39286-3_710.1007/978-3-642-39286-3_7Search in Google Scholar

[5] I. Gorgol, Turán numbers for disjoint copies of graphs, Graphs Combin. 27 (2011) 661–667. doi:10.1007/s00373-010-0999-510.1007/s00373-010-0999-5Search in Google Scholar

[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. doi:10.1137/14098284210.1137/140982842Search in Google Scholar

[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. doi:10.1137/14098285410.1137/140982854Search in Google Scholar

[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. doi:10.1137/14098286610.1137/140982866Search in Google Scholar

[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. doi:10.1137/14098287810.1137/140982878Search in Google Scholar

[10] Y. Lan, T. Li, Y. Shi and J. Tu, The Turán number of star forests, Appl. Math. Comput. 348 (2019) 270–274. doi:10.1016/j.amc.2018.12.00410.1016/j.amc.2018.12.004Search in Google Scholar

[11] S.-S. Li and J.-H. Yin, Two results about the Turán number of star forests, Discrete Math. 343 (2020) 111702. doi:10.1016/j.disc.2019.11170210.1016/j.disc.2019.111702Search in Google Scholar

[12] B. Lidický, H. Liu and C. Palmer, On the Turán number of forests, Electron. J. Combin. 20 (2013) #P62. doi:10.37236/314210.37236/3142Search in Google Scholar

[13] B. Ning and J. Wang, The formula for Turán number of spanning linear forests, Discrete Math. 343 (2020) 111924. doi:10.1016/j.disc.2020.11192410.1016/j.disc.2020.111924Search in Google Scholar

[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.Search in Google Scholar

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

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

[17] J. Wang and W. Yang, The Turán number for spanning linear forests, Discrete Appl. Math. 254 (2019) 291–294. doi:10.1016/j.dam.2018.07.01410.1016/j.dam.2018.07.014Search in Google Scholar

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo