On fan-wheel and tree-wheel Ramsey numbers

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

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)2284-2287
Number of pages7
JournalDiscrete mathematics
Volume339
Issue number9
Early online date6 May 2016
DOIs
Publication statusPublished - 6 Sep 2016

Fingerprint

Ramsey number
Wheel
Fans
Wheels
Subgraph
Odd
Graph in graph theory
Complement
Fan
Denote
Integer

Keywords

  • Fan
  • Tree
  • Ramsey number
  • Wheel

Cite this

Zhang, Yanbo ; Zhang, Yanbo ; Broersma, Haitze J. ; Chen, Yaojun. / On fan-wheel and tree-wheel Ramsey numbers. In: Discrete mathematics. 2016 ; Vol. 339, No. 9. pp. 2284-2287.
@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{\'o}s Conjecture holds.",
keywords = "Fan, Tree, Ramsey number, Wheel",
author = "Yanbo Zhang and Yanbo Zhang and Broersma, {Haitze J.} and Yaojun Chen",
year = "2016",
month = "9",
day = "6",
doi = "10.1016/j.disc.2016.03.013",
language = "English",
volume = "339",
pages = "2284--2287",
journal = "Discrete mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "9",

}

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: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Zhang, Yanbo

AU - Zhang, Yanbo

AU - Broersma, Haitze J.

AU - Chen, Yaojun

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 - Fan

KW - Tree

KW - Ramsey number

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

JF - Discrete mathematics

SN - 0012-365X

IS - 9

ER -