The maximum number of edges in a $\{K_{r+1},M_{k+1}\}$-free graph
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1617-1629
Voir la notice de l'article provenant de la source Library of Science
Let G be a graph and ℱ be a family of graphs. We say G is ℱ-free if it does not contain F as subgraph for any F∈ℱ. The Turán number ex(n,ℱ) is defined as the maximum number of edges in an ℱ-free graph on n vertices. Let K_r+1 denote the complete graph on r+1 vertices and let M_k+1 denote the graph on 2k+2 vertices with k+1 pairwise disjoint edges. By using the alternating path technique and the Zykov symmetrization, we determine that for n gt;3k, ex(n, {M_k+1,K_r+1})= t_r-1(k)+k(n-k),
where t_r-1(k) is the number of edges in an (r-1)-partite k-vertex Turán graph. Let ν(G), τ(G) denote the matching number and the vertex cover number of G, respectively. For n≥ 2k, we prove that if ν(G)≤ k and τ(G)≥ k+r, then e(G)≤max{2k+12, k+r+12+(k-r)(n-k-r-1)}.
Keywords:
Tur\'{a}n number, alternating path, Zykov symmetrization
@article{DMGT_2024_44_4_a20,
author = {Fu, Lingting and Wang, Jian and Yang, Weihua},
title = {The maximum number of edges in a $\{K_{r+1},M_{k+1}\}$-free graph},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {1617--1629},
publisher = {mathdoc},
volume = {44},
number = {4},
year = {2024},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a20/}
}
TY - JOUR
AU - Fu, Lingting
AU - Wang, Jian
AU - Yang, Weihua
TI - The maximum number of edges in a $\{K_{r+1},M_{k+1}\}$-free graph
JO - Discussiones Mathematicae. Graph Theory
PY - 2024
SP - 1617
EP - 1629
VL - 44
IS - 4
PB - mathdoc
UR - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a20/
LA - en
ID - DMGT_2024_44_4_a20
ER -
%0 Journal Article
%A Fu, Lingting
%A Wang, Jian
%A Yang, Weihua
%T The maximum number of edges in a $\{K_{r+1},M_{k+1}\}$-free graph
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1617-1629
%V 44
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a20/
%G en
%F DMGT_2024_44_4_a20
Fu, Lingting; Wang, Jian; Yang, Weihua. The maximum number of edges in a $\{K_{r+1},M_{k+1}\}$-free graph. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1617-1629. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a20/