Turan numbers of theta graphs

被引：17
作者：
Bukh, Boris [1 ]
Tait, Michael [2 ]
机构：
[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA
[2] Villanova Univ, Dept Math & Stat, Villanova, PA 19085 USA
来源：
COMBINATORICS PROBABILITY & COMPUTING | 2020年 / 29卷 / 04期
关键词：
EXTREMAL GRAPHS;
D O I：
10.1017/S0963548320000012
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The theta graph Theta(l,t) consists of two vertices joined by t vertex-disjoint paths, each of length l. For fixed odd l and large t, we show that the largest graph not containing Theta(l,t) has atmost c(l)t(1-1/l)n(1+1/l) edges and that this is tight apart from the value of c(l).
引用
收藏
页码：495 / 507
页数：13
相关论文
共 31 条
[1]   The difference between consecutive primes, II [J].
Baker, RC ;
Harman, G ;
Pintz, J .
PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 2001, 83 :532-562
[2]   MINIMAL REGULAR GRAPHS OF GIRTHS 8 AND 12 [J].
BENSON, CT .
CANADIAN JOURNAL OF MATHEMATICS, 1966, 18 (05) :1091-&
[3]   TURAN NUMBERS FOR FREE GRAPHS: TOPOLOGICAL OBSTRUCTIONS AND ALGEBRAIC CONSTRUCTIONS [J].
Blagojevic, Pavle V. M. ;
Bukh, Boris ;
Karasev, Roman .
ISRAEL JOURNAL OF MATHEMATICS, 2013, 197 (01) :199-214
[4]  
Bondy J. A., 1974, Journal of Combinatorial Theory, Series B, V16, P97, DOI 10.1016/0095-8956(74)90052-5
[5]   ON GRAPHS THAT DO NOT CONTAIN A THOMSEN GRAPH [J].
BROWN, WG .
CANADIAN MATHEMATICAL BULLETIN, 1966, 9 (03) :281-&
[6]   Rational exponents in extremal graph theory [J].
Bukh, Boris ;
Conlon, David .
JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY, 2018, 20 (07) :1747-1757
[7]   A Bound on the Number of Edges in Graphs Without an Even Cycle [J].
Bukh, Boris ;
Jiang, Zilin .
COMBINATORICS PROBABILITY & COMPUTING, 2017, 26 (01) :1-15
[8]   Random algebraic construction of extremal graphs [J].
Bukh, Boris .
BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2015, 47 :939-945
[9]  
Conlon D., B LOND MATH SOC
[10]   ON THE STRUCTURE OF LINEAR GRAPHS [J].
ERDOS, P ;
STONE, AH .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (12) :1087-1091
1234