Narrowing down the gap on cycle-star Ramsey numbers

Yanbo Zhang, Haitze J. Broersma, Yaojun Chen

Abstract

Given two graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cm denote a cycle of order m, K1,n a star of order n + 1 and Wn a wheel of order n + 1. Already back in the 1970s, exact values of the Ramsey numbers R(Cm,K1,n) have been determined for all m ≥ 2n and for all odd m ≤ 2n − 1, but for even m < 2n not many exact values are known. In this paper, we use a result of Bondy on pancyclicity to fill a considerable part of this gap. We show that R(Cm,K1,n) = 2n for even m with n < m < 2n, and that R(Cm,K1,n) = 2m−1 for even m with 3n/4+1 ≤ m ≤ n. In addition, we determine another six formerly unknown exact values of Ramsey numbers, namely R(C6,K1,n) for 7 ≤ n ≤ 11, and R(C6,W9).
Original languageUndefined
Pages (from-to)481-493
Number of pages13
JournalJournal of combinatorics (Somerville)
Volume7
Issue number2-3
DOIs
StatePublished - Feb 2016

Fingerprint

Ramsey number
Subgraph
Pancyclicity
Graph in graph theory
Wheel
Star
Complement
Odd
Denote
Cycle
Unknown
Integer

Keywords

  • EWI-26877
  • MSC-05C
  • Cycle
  • IR-100080
  • Star
  • METIS-316849
  • Ramsey number

Cite this

Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun / Narrowing down the gap on cycle-star Ramsey numbers.

In: Journal of combinatorics (Somerville), Vol. 7, No. 2-3, 02.2016, p. 481-493.

Research output: Scientific - peer-reviewArticle

@article{bbe29708cfc44a79bb61877c2cfcfdbf,
title = "Narrowing down the gap on cycle-star Ramsey numbers",
abstract = "Given two graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cm denote a cycle of order m, K1,n a star of order n + 1 and Wn a wheel of order n + 1. Already back in the 1970s, exact values of the Ramsey numbers R(Cm,K1,n) have been determined for all m ≥ 2n and for all odd m ≤ 2n − 1, but for even m < 2n not many exact values are known. In this paper, we use a result of Bondy on pancyclicity to fill a considerable part of this gap. We show that R(Cm,K1,n) = 2n for even m with n < m < 2n, and that R(Cm,K1,n) = 2m−1 for even m with 3n/4+1 ≤ m ≤ n. In addition, we determine another six formerly unknown exact values of Ramsey numbers, namely R(C6,K1,n) for 7 ≤ n ≤ 11, and R(C6,W9).",
keywords = "EWI-26877, MSC-05C, Cycle, IR-100080, Star, METIS-316849, Ramsey number",
author = "Yanbo Zhang and Broersma, {Haitze J.} and Yaojun Chen",
note = "eemcs-eprint-26877",
year = "2016",
month = "2",
doi = "10.4310/JOC.2016.v7.n2.a13",
volume = "7",
pages = "481--493",
journal = "Journal of combinatorics (Somerville)",
issn = "2156-3527",
publisher = "American Mathematical Society, International Press",
number = "2-3",

}

Narrowing down the gap on cycle-star Ramsey numbers. / Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun.

In: Journal of combinatorics (Somerville), Vol. 7, No. 2-3, 02.2016, p. 481-493.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - Narrowing down the gap on cycle-star Ramsey numbers

AU - Zhang,Yanbo

AU - Broersma,Haitze J.

AU - Chen,Yaojun

N1 - eemcs-eprint-26877

PY - 2016/2

Y1 - 2016/2

N2 - Given two graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cm denote a cycle of order m, K1,n a star of order n + 1 and Wn a wheel of order n + 1. Already back in the 1970s, exact values of the Ramsey numbers R(Cm,K1,n) have been determined for all m ≥ 2n and for all odd m ≤ 2n − 1, but for even m < 2n not many exact values are known. In this paper, we use a result of Bondy on pancyclicity to fill a considerable part of this gap. We show that R(Cm,K1,n) = 2n for even m with n < m < 2n, and that R(Cm,K1,n) = 2m−1 for even m with 3n/4+1 ≤ m ≤ n. In addition, we determine another six formerly unknown exact values of Ramsey numbers, namely R(C6,K1,n) for 7 ≤ n ≤ 11, and R(C6,W9).

AB - Given two graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cm denote a cycle of order m, K1,n a star of order n + 1 and Wn a wheel of order n + 1. Already back in the 1970s, exact values of the Ramsey numbers R(Cm,K1,n) have been determined for all m ≥ 2n and for all odd m ≤ 2n − 1, but for even m < 2n not many exact values are known. In this paper, we use a result of Bondy on pancyclicity to fill a considerable part of this gap. We show that R(Cm,K1,n) = 2n for even m with n < m < 2n, and that R(Cm,K1,n) = 2m−1 for even m with 3n/4+1 ≤ m ≤ n. In addition, we determine another six formerly unknown exact values of Ramsey numbers, namely R(C6,K1,n) for 7 ≤ n ≤ 11, and R(C6,W9).

KW - EWI-26877

KW - MSC-05C

KW - Cycle

KW - IR-100080

KW - Star

KW - METIS-316849

KW - Ramsey number

U2 - 10.4310/JOC.2016.v7.n2.a13

DO - 10.4310/JOC.2016.v7.n2.a13

M3 - Article

VL - 7

SP - 481

EP - 493

JO - Journal of combinatorics (Somerville)

T2 - Journal of combinatorics (Somerville)

JF - Journal of combinatorics (Somerville)

SN - 2156-3527

IS - 2-3

ER -