An exact formula for all star-kipas Ramsey numbers

Binlong Li; Yanbo Zhang; Hajo Broersma

doi:10.1007/s00373-016-1746-3

An exact formula for all star-kipas Ramsey numbers

Binlong Li, Yanbo Zhang, Hajo Broersma

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

59 Downloads (Pure)

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 language	English
Pages (from-to)	141-148
Number of pages	8
Journal	Graphs and combinatorics
Volume	33
Issue number	1
DOIs	https://doi.org/10.1007/s00373-016-1746-3
Publication status	Published - Jan 2017

Keywords

MSC-05C
Wheel
Kipas
Star
Ramsey number

Access to Document

10.1007/s00373-016-1746-3

Li2017exactFinal published version, 357 KB

Cite this

@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 = "MSC-05C, Wheel, Kipas, Star, Ramsey number",

author = "Binlong Li and Yanbo Zhang and Hajo Broersma",

note = "Open Access ",

year = "2017",

month = jan,

doi = "10.1007/s00373-016-1746-3",

language = "English",

volume = "33",

pages = "141--148",

journal = "Graphs and combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

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 - MSC-05C

KW - Wheel

KW - Kipas

KW - Star

KW - Ramsey number

U2 - 10.1007/s00373-016-1746-3

DO - 10.1007/s00373-016-1746-3

M3 - Article

SN - 0911-0119

VL - 33

SP - 141

EP - 148

JO - Graphs and combinatorics

JF - Graphs and combinatorics

IS - 1

ER -

An exact formula for all star-kipas Ramsey numbers

Abstract

Keywords

Access to Document

Fingerprint

Cite this