Geodesic
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 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2024},
     volume = {44},
     number = {4},
     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
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
%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/

[1] H.L. Abbott, D. Hanson and N. Sauer, Intersection theorems for systems of sets, J. Combin. Theory Ser. A 12 (1972) 381–389. https://doi.org/10.1016/0097-3165(72)90103-3

[2] J. Akiyama and P. Frankl, On the size of graphs with complete-factors, J. Graph Theory 9 (1985) 197–201. https://doi.org/10.1002/jgt.3190090117

[3] N. Alon and P. Frankl, Turán graphs with bounded matching number (2022). arXiv: 2210.15076

[4] N. Alon, M. Krivelevich and B. Sudakov, Turán numbers of bipartite graphs and related Ramsey-type questions, Combin. Probab. Comput. 12 (2003) 477–494. https://doi.org/10.1017/S0963548303005741

[5] I. Anderson, Perfect matching of a graph, J. Combin. Theory. Ser. B 10 (1971) 183–186. https://doi.org/10.1016/0095-8956(71)90041-4

[6] C. Berge, Sur le couplage maximum d'un graphe, C.R. Acad. Sci. Paris 247 (1958) 2–29.

[7] C. Berge, The Theory of Graphs and its Applications (Methuen, London and Wiley, New York, 1962).

[8] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[9] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver, Combinatorial Optimization (Wiley, 1998). https://doi.org/10.1002/9781118033142

[10] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta. Math. Hungar. 10 (1959) 337–356. https://doi.org/10.1007/BF02024498

[11] Z. Füredi, On a Turán type problem of Erdős, Combinatorica 11 (1991) 75–79. https://doi.org/10.1007/BF01375476

[12] F. Gavril, Testing for equality between maximum matching and minimum node covering, Inform. Process. Lett. 6 (1977) 199–202. https://doi.org/10.1016/0020-0190(77)90068-0

[13] P. Hall, On representatives of subsets, in: Classic Papers in Combinatorics, I. Gessel and G.-C. Rota (Ed(s)), (Modern Birkkäuser Classic 1987) 58–62. https://doi.org/10.1007/978-0-8176-4842-8_4

[14] D. König, Theorie der endlichen und unendlichen Graphen (Akademischen Verlagsgesellchaft, Leipig, 1936).

[15] P. Kővári, V.T. Sós and P. Turán, On a problem of Zarankiewicz, Colloq. Math. 3 (1954) 50–57.

[16] W. Mantel, Problem 28, Wiskundige Opgaven 10 (1907) 60–61.

[17] M.D. Plummer and L. Lovász, Matching Theory (Elsevier, 1986).

[18] A. Sidorenko, What we know and what we do not know about Turán numbers, Graphs Combin. 11 (1995) 179–199. https://doi.org/10.1007/BF01929486

[19] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436–452, in Hungarian.

[20] W.T. Tutte, The factorization of linear graphs, J. Lond. Math. Soc. 22 (1947) 107–111. https://doi.org/10.1112/jlms/s1-22.2.107

[21] D.B. West, A short proof of the Berge-Tutte Formula and the Gallai-Edmonds Structure Theorem, European J. Combin. 32 (2011) 674–676. https://doi.org/10.1016/j.ejc.2011.01.009

[22] L.-T. Yuan, Extremal graphs for the k-flower, J. Graph Theory 89 (2018) 26–39. https://doi.org/10.1002/jgt.22237

[23] L.-T. Yuan, Extremal graphs for odd wheels, J. Graph Theory 98 (2021) 691–707. https://doi.org/10.1002/jgt.22727

[24] L.-T. Yuan, Extremal graphs for edge blow-up of graphs, J. Combin. Theory. Ser. B. 152 (2022) 379–398. https://doi.org/10.1016/j.jctb.2021.10.006

[25] A.A. Zykov, On some properties of linear complexes, Mat. Sb. (N.S.) 24(66) (1949) 163–188, in Russian.