1. bookVolume 42 (2022): Issue 4 (November 2022)
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 for 4 · S1

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1119 - 1128
Received: 25 Oct 2019
Accepted: 09 May 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 denote the star on + 1 vertices, and let k · S denote k disjoint copies of S. Erdős and Gallai determined the value ex(n, k · S1) for all positive integers k and n. Yuan and Zhang determined the value ex(n, k · S2) and characterized all extremal graphs for all positive integers k and n. Recently, Lan et al. determined the value ex(n, 2 · S3) for all positive integers n, and Li and Yin determined the values ex(n, k · S) for k = 2, 3 and all positive integers and n. In this paper, we further determine the value ex(n, 4 · S) for all positive integers and almost all n, improving one of the results of Lidický et al.

Keywords

MSC 2010

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, 1976). Search in Google Scholar

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

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

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

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

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

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

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

[9] P. Turán, An extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436–452, in Hungarian. Search in Google Scholar

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo