An exact formula for all star-kipas Ramsey numbers

Binlong Li, Yanbo Zhang, Hajo Broersma

Abstract

Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or the complement of G contains a G2. A complete bipartite graph K1,n is called a star. The kipas of order n+1 is the graph obtained from a path of order n by adding a new vertex and joining it to all the vertices of the path. Alternatively, a kipas is a wheel with one edge on the rim deleted. Whereas for star-wheel Ramsey numbers not all exact values are known to date, in contrast we determine all exact values of star-kipas Ramsey numbers.
Original languageEnglish
Pages (from-to)141-148
Number of pages8
JournalGraphs and combinatorics
Volume33
Issue number1
DOIs
StatePublished - Jan 2017

Fingerprint

Stars
Wheels
Joining

Keywords

  • EWI-27594
  • MSC-05C
  • Wheel
  • IR-104073
  • Kipas
  • Star
  • Ramsey number

Cite this

Li, Binlong; Zhang, Yanbo; Broersma, Hajo / An exact formula for all star-kipas Ramsey numbers.

In: Graphs and combinatorics, Vol. 33, No. 1, 01.2017, p. 141-148.

Research output: Scientific - peer-reviewArticle

@article{976f2e5d244e4345b436a4c8cc96b8e3,
title = "An exact formula for all star-kipas Ramsey numbers",
abstract = "Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or the complement of G contains a G2. A complete bipartite graph K1,n is called a star. The kipas of order n+1 is the graph obtained from a path of order n by adding a new vertex and joining it to all the vertices of the path. Alternatively, a kipas is a wheel with one edge on the rim deleted. Whereas for star-wheel Ramsey numbers not all exact values are known to date, in contrast we determine all exact values of star-kipas Ramsey numbers.",
keywords = "EWI-27594, MSC-05C, Wheel, IR-104073, Kipas, Star, Ramsey number",
author = "Binlong Li and Yanbo Zhang and Hajo Broersma",
note = "Open Access",
year = "2017",
month = "1",
doi = "10.1007/s00373-016-1746-3",
volume = "33",
pages = "141--148",
journal = "Graphs and combinatorics",
issn = "0911-0119",
publisher = "Springer Japan",
number = "1",

}

An exact formula for all star-kipas Ramsey numbers. / Li, Binlong; Zhang, Yanbo; Broersma, Hajo.

In: Graphs and combinatorics, Vol. 33, No. 1, 01.2017, p. 141-148.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - An exact formula for all star-kipas Ramsey numbers

AU - Li,Binlong

AU - Zhang,Yanbo

AU - Broersma,Hajo

N1 - Open Access

PY - 2017/1

Y1 - 2017/1

N2 - Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or the complement of G contains a G2. A complete bipartite graph K1,n is called a star. The kipas of order n+1 is the graph obtained from a path of order n by adding a new vertex and joining it to all the vertices of the path. Alternatively, a kipas is a wheel with one edge on the rim deleted. Whereas for star-wheel Ramsey numbers not all exact values are known to date, in contrast we determine all exact values of star-kipas Ramsey numbers.

AB - Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or the complement of G contains a G2. A complete bipartite graph K1,n is called a star. The kipas of order n+1 is the graph obtained from a path of order n by adding a new vertex and joining it to all the vertices of the path. Alternatively, a kipas is a wheel with one edge on the rim deleted. Whereas for star-wheel Ramsey numbers not all exact values are known to date, in contrast we determine all exact values of star-kipas Ramsey numbers.

KW - EWI-27594

KW - MSC-05C

KW - Wheel

KW - IR-104073

KW - Kipas

KW - Star

KW - Ramsey number

U2 - 10.1007/s00373-016-1746-3

DO - 10.1007/s00373-016-1746-3

M3 - Article

VL - 33

SP - 141

EP - 148

JO - Graphs and combinatorics

T2 - Graphs and combinatorics

JF - Graphs and combinatorics

SN - 0911-0119

IS - 1

ER -