The Ramsey numbers R(Cm, K7) and R(C7, K8)

被引：15

作者：

Chen, Yaojun ^{[1
]}

Cheng, T. C. Edwin ^{[2
]}

Zhang, Yunqing ^{[1
]}

机构：

[1] Nanjing Univ, Dept Math, Nanjing 210093, Peoples R China

[2] Hong Kong Polytech Univ, Dept Logist, Kowloon, Hong Kong, Peoples R China

来源：

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

基金：

中国国家自然科学基金;

关键词：

D O I：

10.1016/j.ejc.2007.05.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For two given graphs G(1) and G(2), the Ramsey number R(G(1), G(2)) is the smallest integer it such that for any graph G of order n, either G contains G(1) or the complement of G contains G(2). Let C-m denote a cycle of length in and K-n a complete graph of order n. In this paper we show that R(C-m, K-7) = 6m - 5 for m >= 7 and R(C-7, K-8) = 43, with the former result confirming a conjecture due to Erdos, Faudree, Rousseau and Schelp, that R(C,,,, Kn) = (m - 1)(n - 1) + 1 for m >= n >= 3 and (m, n) not equal (3, 3) in the case where n = 7. (c) 2007 Elsevier Ltd. All rights reserved.

引用

页码：1337 / 1352

页数：16

共 11 条

[1]

Bollobas B. C. J., 2000, AUSTRALAS J COMBIN, V22, P63

[2]

Bondy J.A., 2008, GRAD TEXTS MATH

[3] The Ramsey numbers for a cycle of length six or seven versus a clique of order seven [J].

Cheng, T. C. Edwin ;

Chen, Yaojun ;

Zhang, Yunqing ;

Ng, C. T. .

DISCRETE MATHEMATICS, 2007, 307 (9-10) :1047-1053

[4]

Chvatal V., 1972, DISCRETE MATH, V2, P111, DOI DOI 10.1016/0012-365X(72)90079-9

[5]

Faudree R. J., 1974, Discrete Mathematics, V8, P313, DOI 10.1016/0012-365X(74)90151-4

[6]

Ore O., 1960, AM MATH MONTHLY, V67, P55, DOI [10.2307/2308928, DOI 10.2307/2308928]

[7]

RADZISZOWSKI SP, 2006, ELECTRON J COMB, DOI UNSP DS1.11

[8]

Rosta V., 1973, Journal of Combinatorial Theory, Series B, V15, P94, DOI 10.1016/0095-8956(73)90035-X

[9] All cycle-complete graph Ramsey numbers r(Cm, K6) [J].

Schiermeyer, I .

JOURNAL OF GRAPH THEORY, 2003, 44 (04) :251-260

[10]

Yang WY, 1999, APPL MATH MECH-ENGL, V20, P205

← 1 2 →