Extremal graphs for odd wheels

被引:18
作者
Yuan, Long-Tu [1 ]
机构
[1] East China Normal Univ, Sch Math & Sci, Dept Appl Math, 500 Dongchuan Rd, Shanghai 200240, Peoples R China
基金
中国国家自然科学基金;
关键词
decomposition family; Turan number; wheels; EDGES;
D O I
10.1002/jgt.22727
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a graph H, the Turan number of H, denoted by ex(n,H), is the maximum number of edges of an n-vertex H-free graph. Let g(n,H) denote the maximum number of edges not contained in any monochromatic copy of H in a 2-edge-coloring of Kn. A wheel Wm is a graph formed by connecting a single vertex to all vertices of a cycle of length m-1. The Turan number of W2k was determined by Simonovits in 1960s. In this paper, we determine ex(n,W2k+1) when n is sufficiently large. We also show that, for sufficient large n, g(n,W2k+1)=ex(n,W2k+1) which confirms a conjecture posed by Keevash and Sudakov for odd wheels.
引用
收藏
页码:691 / 707
页数:17
相关论文
共 22 条
[1]   Extremal graphs for intersecting cliques [J].
Chen, GT ;
Gould, RJ ;
Pfender, F ;
Wei, B .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 89 (02) :159-171
[2]   Turan numbers for odd wheels [J].
Dzido, Tomasz ;
Jastrzebski, Andrzej .
DISCRETE MATHEMATICS, 2018, 341 (04) :1150-1154
[3]  
Erdo P., 1966, Studia Sci. Math. Hungar., V1, P51
[4]   EXTREMAL GRAPHS FOR INTERSECTING TRIANGLES [J].
ERDOS, P ;
FUREDI, Z ;
GOULD, RJ ;
GUNDERSON, DS .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 64 (01) :89-100
[5]   EXTREMAL GRAPH PROBLEM [J].
ERDOS, P ;
SIMONOVI.M .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1972, 22 (3-4) :275-&
[6]   ON THE STRUCTURE OF LINEAR GRAPHS [J].
ERDOS, P ;
STONE, AH .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (12) :1087-1091
[7]  
Erds P., 1959, ACTA MATH ACAD SCI H, V10, P337, DOI DOI 10.1007/BF02024498
[8]   Stability theorems for cancellative hypergraphs [J].
Keevash, P ;
Mubayi, D .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 92 (01) :163-175
[9]   On the number of edges not covered by monochromatic copies of a fixed graph [J].
Keevash, P ;
Sudakov, B .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 90 (01) :41-53
[10]  
Kovari Tamas, 1954, COLLOQ MATH-WARSAW, V3, P50