Turan number of complete bipartite graphs with bounded matching number

被引:0
作者
Luo, Huan [1 ]
Zhao, Xiamiao [1 ]
Lu, Mei [1 ]
机构
[1] Tsinghua Univ, Dept Math Sci, Beijing 100084, Peoples R China
基金
中国国家自然科学基金;
关键词
Turan number; Matching number; Bipartite graph; Extremal problem;
D O I
10.1016/j.disc.2025.114552
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let F be a family of graphs. A graph Gis F-free if Gdoes not contain any F is an element of F as a subgraph. The Turan number ex(n, F) is the maximum number of edges in an n-vertex F-free graph. Let Msbe the matching consisting of sindependent edges. Recently, Alon and Frankl determined the exact value of ex(n,{K-m, Ms+1}). Gerbner obtained several results about ex(n,{F, Ms+1}) when Fsatisfies certain properties. In this paper, we determine the exact value of ex(n,{K-l,K-t, Ms+1}) when s, nare large enough for every 3 <= l <= t. When nis large enough, we also show that ex(n,{K-2,K-2, Ms+1})= n+ ((s)(2)) - inverted right perpendicular s/2 inverted left perpendicular for s= 12and ex(n,{K-2,K- t, Ms+1})= n+(t-1)((s)(2)) - inverted right perpendicular s/2 inverted left perpendicular when t >= 3 and sis large enough. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
引用
收藏
页数:11
相关论文
共 16 条
[1]   Norm-graphs:: Variations and applications [J].
Alon, N ;
Rónyai, L ;
Szabó, T .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 76 (02) :280-290
[2]   Turan numbers of bipartite graphs and related Ramsey-Type questions [J].
Alon, N ;
Krivelevich, M ;
Sudakov, B .
COMBINATORICS PROBABILITY & COMPUTING, 2003, 12 (5-6) :477-494
[3]   Turán graphs with bounded matching number [J].
Alon, Noga ;
Frankl, Peter .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 165 :223-229
[4]  
[Anonymous], 2009, Matching theory
[5]   ON GRAPHS THAT DO NOT CONTAIN A THOMSEN GRAPH [J].
BROWN, WG .
CANADIAN MATHEMATICAL BULLETIN, 1966, 9 (03) :281-&
[6]  
Bukh B, 2022, Arxiv, DOI arXiv:2107.04167
[7]   DEGREES AND MATCHINGS [J].
CHVATAL, V ;
HANSON, D .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1976, 20 (02) :128-138
[8]  
Erdos P., 1966, STUD SCI MATH HUNG, V1, P215
[9]  
Erdos P., 1961, PUBLICATIONS MATH I, V6, P181
[10]   New asymptotics for bipartite Turan numbers [J].
Furedi, Z .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1996, 75 (01) :141-144