Bounds for Ramsey numbers of complete graphs dropping an edge

被引：7

作者：

Li, Yusheng ^{[1
]}

Shen, Jian ^{[1
]}

机构：

[1] Tongji Univ, Dept Math, Shanghai 200092, Peoples R China

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2008年 / 29卷 / 01期

基金：

中国国家自然科学基金;

关键词：

D O I：

10.1016/j.ejc.2006.12.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let K-n - e be a graph obtained from a complete graph of order n by dropping an edge, and let G(p) be a Paley graph of order p. It is shown that if G(p) contains no K-n -e, then r(Kn+l -e) >= 2p+ 1. For example, G1493 contains no K-13 - e, so r(K-14 - e) >= 2987, improving the old bound 2557. It is also shown that r((K) over bar (2) + G) < 4(r)(G, <(K)over bar>(2) + G) - 2, implying that r(K-n - e) <= 4r(Kn-2, K-n - e) - 2. (c) 2007 Elsevier Ltd. All rights reserved.

引用

页码：88 / 94

页数：7

共 10 条

[1] GENERALIZED RAMSEY THEORY FOR GRAPHS .2. SMALL DIAGONAL NUMBERS [J].

CHVATAL, V ;

HARARY, F .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1972, 32 (02) :389-+

[2] THE RAMSEY NUMBER OF K5-E [J].

CLAPHAM, C ;

EXOO, G ;

HARBORTH, H ;

MENGERSEN, I ;

SHEEHAN, J .

JOURNAL OF GRAPH THEORY, 1989, 13 (01) :7-15

[3]

Exoo G, 2000, NEW LOWER BOUNDS TAB

[4]

EXOO G, 1991, P APPL MATH, V5, pCH19

[5]

HUANG YR, 1998, EUROPEAN J COMBIN, V19, P391

[6] An upper bound for Ramsey numbers [J].

Li, YS ;

Rousseau, CC ;

Zang, WN .

APPLIED MATHEMATICS LETTERS, 2004, 17 (06) :663-665

[7] LOWER BOUNDS FOR RAMSEY NUMBERS AND ASSOCIATION SCHEMES [J].

MATHON, R .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1987, 42 (01) :122-127

[8] Tidier examples for lower bounds on diagonal Ramsey numbers [J].

McDiarmid, C ;

Steger, A .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1996, 74 (01) :147-152

[9]

SHEARER J, 1986, J COMB THEORY A, V42, P213

[10]

SHI LS, 2001, UNPUB UPPER BOUND FO

← 1 →