An exact formula for all star-kipas Ramsey numbers

Binlong Li, Yanbo Zhang, Hajo Broersma

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
12 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 languageEnglish
Pages (from-to)141-148
Number of pages8
JournalGraphs and combinatorics
Volume33
Issue number1
DOIs
Publication statusPublished - Jan 2017

Fingerprint

Ramsey number
Stars
Star
Wheel
Wheels
Graph in graph theory
Path
Complete Bipartite Graph
Joining
Complement
Integer
Vertex of a graph

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. 2017 ; Vol. 33, No. 1. pp. 141-148.
@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",
language = "English",
volume = "33",
pages = "141--148",
journal = "Graphs and combinatorics",
issn = "0911-0119",
publisher = "Springer",
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: Contribution to journalArticleAcademicpeer-review

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

JF - Graphs and combinatorics

SN - 0911-0119

IS - 1

ER -