Article in press
Authors:
Title:
Generalized Turán problems for disjoint even wheels, and for disjoint bowties
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-10-03 , Revised: 2025-06-28 , Accepted: 2025-07-03 , Available online: 2025-08-20 , https://doi.org/10.7151/dmgt.2596
Abstract:
Given graphs $T$ and $F$, the generalized Turán number $ex(n,T,F)$ is
the maximum possible number of copies of $T$ in an $F$-free graph on $n$ vertices.
Let $W_{n}$ be the wheel graph obtained from a cycle $C_{n-1}$
and an extra vertex $v$ by joining $v$ and all vertices of $C_{n-1}$. Let
$\ell \cdot F$ be the graph consisting of $\ell$ vertex-disjoint copies of $F$.
A graph consisting of two triangles which intersect in exactly one common
vertex is called a bowtie and denoted by $F_{2}$.
In this paper, we determine the exact values of $ex(n,K_{r},(\ell+1) \cdot
W_{2k})$ for $4 \leq r \leq \ell+3$, and $ex(n,K_{r},(\ell+1) \cdot F_{2})$ for
$3 \leq r \leq \ell+2$, and characterize all their extremal graphs.
Keywords:
generalized Turán number, extremal graph, even wheel, bowtie
References:
- N. Alon and C. Shikhelman, Many $T$ copies in $H$-free graphs, J. Combin. Theory Ser. B 121 (2016) 146–172.
https://doi.org/10.1016/j.jctb.2016.03.004 - J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer London, 2008).
- T. Dzido, A note on Turán numbers for even wheels, Graphs Combin. 29(5) (2013) 1305–1309.
https://doi.org/10.1007/s00373-012-1212-9 - 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 - P. Erdős, Z. Füredi, R.J. Gould and D.S. Gunderson, Extremal graphs for intersecting triangles, J. Combin. Theory Ser. B 64 (1995) 89–100.
https://doi.org/10.1006/jctb.1995.1026 - Z. Füredi and D.S. Gunderson, Extremal numbers for odd cycles, Combin. Probab. Comput. 24 (2015) 641–645.
https://doi.org/10.1017/S0963548314000601 - J. Gao, Z. Wu and Y. Xu, Counting cliques without generalized theta graphs (2023).
arXiv: 2311.15289 - D. Gerbner, A. Methuku and M. Vizer, Generalized Turán problems for disjoint copies of graphs, Discrete Math. 342 (2019) 3130–3141.
https://doi.org/10.1016/j.disc.2019.06.022 - D. Gerbner, Generalized Turán results for disjoint cliques, Discrete Math. 347(7) (2024) 114024.
https://doi.org/10.1016/j.disc.2024.114024 - D. Gerbner, E. Győri, A. Methuku and M. Vizer, Generalized Turán problems for even cycles, J. Combin. Theory Ser. B 145 (2020) 169–213.
https://doi.org/10.1016/j.jctb.2020.05.005 - J. Hou, C. Yang and Q. Zeng, Counting triangles in graphs without vertex disjoint odd cycles, Discrete Math. 347(7) (2024) 114015.
https://doi.org/10.1016/j.disc.2024.114015 - J. Hou, H. Li, X. Liu, L.-T. Yuan and Y. Zhang, A step towards a general density Corrádi–Hajnal theorem, Canad. J. Math. (2025) 1–36.
https://doi.org/10.4153/S0008414X25000197 - E.L.L. Liu and J. Wang, The generalized Turán problem of two intersecting cliques, Discuss. Math. Graph Theory 45 (2025) 565–594.
https://doi.org/10.7151/dmgt.2544 - J. Ma and Y. Qiu, Some sharp results on the generalized Turán numbers, European J. Combin. 84 (2020) 103026.
https://doi.org/10.1016/j.ejc.2019.103026 - V.T. Sós, Remarks on the connection of graph theory, finite geometry and block designs, in: Colloq. Internat. Teorie Combin. II, Roma, 1973, Atti dei Convegni Lincei 17, (Accad. Naz. Lincei, Rome 1976) 223–233.
- M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs, Proc. Colloq., Tihany, 1966, (Academic Press, New York 1968) 279–319.
- P. Turán, On an extremal problem in graph theory, Math. Fiz. Lapok 48 (1941) 436–452, in Hungarian.
- C. Xiao and O. Zamora, A note on the Turán number of disjoint union of wheels, Discrete Math. 344(11) (2021) 112570.
https://doi.org/10.1016/j.disc.2021.112570 - L.-T. Yuan, Extremal graphs for odd wheels, J. Graph Theory 98 (2021) 691–707.
https://doi.org/10.1002/jgt.22727 - F. Zhang, Y. Chen, E. Győri and X. Zhu, Maximum cliques in a graph without disjoint given subgraph, Discrete Math. 347(4) (2024) 113863.
https://doi.org/10.1016/j.disc.2023.113863 - X. Zhu, Y. Chen, D. Gerbner, E. Győri and H.H. Karim, The maximum number of triangles in $F_k$-free graphs, European J. Combin. 114 (2023) 103793.
https://doi.org/10.1016/j.ejc.2023.103793 - X. Zhu and Y. Chen, Generalized Turán number for linear forests, Discrete Math. 345(10) (2022) 112997.
https://doi.org/10.1016/j.disc.2022.112997
Close