On fan-wheel and tree-wheel Ramsey numbers

Yanbo Zhang, Yanbo Zhang, Haitze J. Broersma, Yaojun Chen

Abstract

For graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that, for any graph G of order N, G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn denote a tree of order n, Wn a wheel of order n+1 and Fn a fan of order 2n+1. We establish Ramsey numbers for fans and trees versus wheels of even order, thereby extending several known results. In particular, we prove that R(Fn,Wm)=6n+1 for odd m≥3 and n≥(5m+3)/4, and that R(Tn,Wm)=3n−2 for odd m≥3 and n≥m−2, and Tn being a tree for which the Erdős–Sós Conjecture holds.
Original languageUndefined
Pages (from-to)2284-2287
Number of pages7
JournalDiscrete mathematics
Volume339
Issue number9
DOIs
StatePublished - 6 Sep 2016

Fingerprint

Fans
Wheels

Keywords

  • MSC-05C
  • EWI-27003
  • Fan
  • METIS-317199
  • Tree
  • Ramsey number
  • IR-100652
  • Wheel

Cite this

Zhang, Yanbo; Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun / On fan-wheel and tree-wheel Ramsey numbers.

In: Discrete mathematics, Vol. 339, No. 9, 06.09.2016, p. 2284-2287.

Research output: Scientific - peer-reviewArticle

@article{a9e207190efe4426b04a7268767e3fab,
title = "On fan-wheel and tree-wheel Ramsey numbers",
abstract = "For graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that, for any graph G of order N, G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn denote a tree of order n, Wn a wheel of order n+1 and Fn a fan of order 2n+1. We establish Ramsey numbers for fans and trees versus wheels of even order, thereby extending several known results. In particular, we prove that R(Fn,Wm)=6n+1 for odd m≥3 and n≥(5m+3)/4, and that R(Tn,Wm)=3n−2 for odd m≥3 and n≥m−2, and Tn being a tree for which the Erdős–Sós Conjecture holds.",
keywords = "MSC-05C, EWI-27003, Fan, METIS-317199, Tree, Ramsey number, IR-100652, Wheel",
author = "Yanbo Zhang and Yanbo Zhang and Broersma, {Haitze J.} and Yaojun Chen",
note = "eemcs-eprint-27003",
year = "2016",
month = "9",
doi = "10.1016/j.disc.2016.03.013",
volume = "339",
pages = "2284--2287",
journal = "Discrete mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "9",

}

Zhang, Y, Zhang, Y, Broersma, HJ & Chen, Y 2016, 'On fan-wheel and tree-wheel Ramsey numbers' Discrete mathematics, vol 339, no. 9, pp. 2284-2287. DOI: 10.1016/j.disc.2016.03.013

On fan-wheel and tree-wheel Ramsey numbers. / Zhang, Yanbo; Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun.

In: Discrete mathematics, Vol. 339, No. 9, 06.09.2016, p. 2284-2287.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - On fan-wheel and tree-wheel Ramsey numbers

AU - Zhang,Yanbo

AU - Zhang,Yanbo

AU - Broersma,Haitze J.

AU - Chen,Yaojun

N1 - eemcs-eprint-27003

PY - 2016/9/6

Y1 - 2016/9/6

N2 - For graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that, for any graph G of order N, G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn denote a tree of order n, Wn a wheel of order n+1 and Fn a fan of order 2n+1. We establish Ramsey numbers for fans and trees versus wheels of even order, thereby extending several known results. In particular, we prove that R(Fn,Wm)=6n+1 for odd m≥3 and n≥(5m+3)/4, and that R(Tn,Wm)=3n−2 for odd m≥3 and n≥m−2, and Tn being a tree for which the Erdős–Sós Conjecture holds.

AB - For graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that, for any graph G of order N, G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn denote a tree of order n, Wn a wheel of order n+1 and Fn a fan of order 2n+1. We establish Ramsey numbers for fans and trees versus wheels of even order, thereby extending several known results. In particular, we prove that R(Fn,Wm)=6n+1 for odd m≥3 and n≥(5m+3)/4, and that R(Tn,Wm)=3n−2 for odd m≥3 and n≥m−2, and Tn being a tree for which the Erdős–Sós Conjecture holds.

KW - MSC-05C

KW - EWI-27003

KW - Fan

KW - METIS-317199

KW - Tree

KW - Ramsey number

KW - IR-100652

KW - Wheel

U2 - 10.1016/j.disc.2016.03.013

DO - 10.1016/j.disc.2016.03.013

M3 - Article

VL - 339

SP - 2284

EP - 2287

JO - Discrete mathematics

T2 - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 9

ER -

Zhang Y, Zhang Y, Broersma HJ, Chen Y. On fan-wheel and tree-wheel Ramsey numbers. Discrete mathematics. 2016 Sep 6;339(9):2284-2287. Available from, DOI: 10.1016/j.disc.2016.03.013