The generalized Turán number of $ 2 S_\ell $

Yanjiao Liu; Jianhua Yin; Yanjiao Liu; Jianhua Yin

doi:10.3934/math.20231205

AIMS Mathematics

2023, Volume 8, Issue 10: 23707-23712. doi: 10.3934/math.20231205

Previous Article Next Article

Research article

The generalized Turán number of $ 2 S_\ell $

Yanjiao Liu ,
Jianhua Yin ^,

School of Mathematics and Statistics, Hainan University, Haikou 570228, China

Received: 15 May 2023 Revised: 16 July 2023 Accepted: 27 July 2023 Published: 02 August 2023
MSC : 05C35

The generalized Turán number $ ex{(n, K_s, H)} $ is defined to be the maximum number of copies of a complete graph $ K_s $ in any $ H $-free graph on $ n $ vertices. Let $ S_\ell $ denote the star on $ \ell+1 $ vertices, and let $ kS_\ell $ denote the disjoint union of $ k $ copies of $ S_\ell $. Gan et al. and Chase determined $ ex(n, K_s, S_\ell) $ for all integers $ s\ge 3 $, $ \ell\ge 1 $ and $ n\ge 1 $. In this paper, we determine $ ex(n, K_s, 2S_\ell) $ for all integers $ s\ge 4 $, $ \ell\ge 1 $ and $ n\ge 1 $.
- generalized Turán number,
- disjoint copies,
- $ 2 S_\ell $
Citation: Yanjiao Liu, Jianhua Yin. The generalized Turán number of $ 2 S_\ell $[J]. AIMS Mathematics, 2023, 8(10): 23707-23712. doi: 10.3934/math.20231205

Related Papers:

Abstract

The generalized Turán number $ ex{(n, K_s, H)} $ is defined to be the maximum number of copies of a complete graph $ K_s $ in any $ H $-free graph on $ n $ vertices. Let $ S_\ell $ denote the star on $ \ell+1 $ vertices, and let $ kS_\ell $ denote the disjoint union of $ k $ copies of $ S_\ell $. Gan et al. and Chase determined $ ex(n, K_s, S_\ell) $ for all integers $ s\ge 3 $, $ \ell\ge 1 $ and $ n\ge 1 $. In this paper, we determine $ ex(n, K_s, 2S_\ell) $ for all integers $ s\ge 4 $, $ \ell\ge 1 $ and $ n\ge 1 $.

References

[1]	J. Bondy, U. Murty, Graph theory with applications, North-Holland: Elsevier Science, 1976.
[2]	D. Chakraborti, D. Chen, Exact results on generalized Erdős-Gallai problems, arXiv: 2006.04681.
[3]	Z. Chase, The maximum number of triangles in a graph of given maximum degree, Advances in Combinatorics, in press. http://dx.doi.org/10.19086/aic.16788
[4]	P. Erdős, T. Gallai, On maximal paths and circuits of graphs, Acta Mathematica Academiae Scientiarum Hungaricae, 10 (1959), 337–356. http://dx.doi.org/10.1007/BF02024498 doi: 10.1007/BF02024498
[5]	W. Gan, P. Loh, B. Sudakov, Maximizing the number of independent sets of a fixed size, Combin. Probab. Comput., 24 (2015), 521–527. http://dx.doi.org/10.1017/S0963548314000546 doi: 10.1017/S0963548314000546
[6]	D. Gerbner, A. Methuku, M. Vizer, Generalized Turán problems for disjoint copies of graphs, Discrete Math., 342 (2019), 3130–3141. http://dx.doi.org/10.1016/j.disc.2019.06.022 doi: 10.1016/j.disc.2019.06.022
[7]	I. Gorgol, Turán numbers for disjoint copies of graphs, Graph. Combinator., 27 (2011), 661–667. http://dx.doi.org/10.1007/s00373-010-0999-5 doi: 10.1007/s00373-010-0999-5
[8]	Y. Lan, T. Li, Y. Shi, J. Tu, The Turán number of star forests, Appl. Math. Comput., 348 (2019), 270–274. http://dx.doi.org/10.1016/j.amc.2018.12.004 doi: 10.1016/j.amc.2018.12.004
[9]	S. Li, J. Yin, J. Li, The Turán number of $kS_\ell$, Discrete Math., 345 (2022), 112653. http://dx.doi.org/10.1016/j.disc.2021.112653 doi: 10.1016/j.disc.2021.112653
[10]	B. Lidický, H. Liu, C. Palmer, On the Turán number of forests, Electron. J. Comb., 20 (2013), 1–13. http://dx.doi.org/10.37236/3142 doi: 10.37236/3142
[11]	R. Luo, The maximum number of cliques in graphs without long cycles, J. Comb. Theory B, 128 (2018), 219–226. http://dx.doi.org/10.1016/j.jctb.2017.08.005 doi: 10.1016/j.jctb.2017.08.005
[12]	M. Simonovits, A method for solving extremal problems in extremal graph theory, In: Theory of graphs, New York: Academic Press, 1968,279–319.
[13]	J. Wang, The shifting method and generalized Turán number of matchings, Eur. J. Combin., 85 (2020), 103057. http://dx.doi.org/10.1016/j.ejc.2019.103057 doi: 10.1016/j.ejc.2019.103057
[14]	L. Yuan, X. Zhang, The Turán number of disjoint copies of paths, Discrete Math., 340 (2017), 132–139. http://dx.doi.org/10.1016/j.disc.2016.08.004 doi: 10.1016/j.disc.2016.08.004
[15]	L. Zhang, L. Wang, J. Zhou, The generalized Turán number of spanning linear forests, Graph. Combinator., 38 (2022), 40. http://dx.doi.org/10.1007/s00373-021-02403-9 doi: 10.1007/s00373-021-02403-9
[16]	X. Zhu, Y. Chen, Generalized Turán number for linear forests, Discrete Math., 345 (2022), 112997. http://dx.doi.org/10.1016/j.disc.2022.112997 doi: 10.1016/j.disc.2022.112997
[17]	X. Zhu, F. Zhang, Y. Chen, Generalized Turán number of even linear forests, Graph. Combinator., 37 (2021), 1437–1449. http://dx.doi.org/10.1007/s00373-021-02329-2 doi: 10.1007/s00373-021-02329-2

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)