An exact formula for all star-kipas Ramsey numbers

Binlong Li, Yanbo Zhang, Haitze J. 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 languageUndefined
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, Haitze J. / An exact formula for all star-kipas Ramsey numbers.

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 Broersma, {Haitze J.}",
note = "Open Access",
year = "2017",
month = "1",
doi = "10.1007/s00373-016-1746-3",
volume = "33",
pages = "141--148",
number = "1",

}

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

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,Haitze J.

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

IS - 1

ER -

Li B, Zhang Y, Broersma HJ. An exact formula for all star-kipas Ramsey numbers. 2017 Jan;33(1):141-148. Available from, DOI: 10.1007/s00373-016-1746-3