• 1 Citations

Abstract

For two given graphs G1 and G2, the Ramsey number R(G1, G2) is the smallest integerN such that, for any graph G of order N, either G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn be a tree of order n, Sn a star of order n, and Fm a fan of order 2m + 1, i.e., m triangles sharing exactly one vertex. In this paper, we prove that R(Tn, Fm) = 2n − 1 for n ≥ 3m^2 − 2m − 1, and if Tn = Sn, then the range can be replaced by n ≥ max{m(m − 1) + 1, 6(m − 1)}, which is tight in some sense.
Original languageUndefined
Pages (from-to)994-999
Number of pages6
JournalDiscrete mathematics
Volume338
Issue number6
DOIs
StatePublished - Jun 2015

Fingerprint

Fans
Stars

Keywords

  • EWI-25790
  • MSC-05C
  • Tree
  • IR-94674
  • Star
  • Fan
  • METIS-312512
  • Ramsey number

Cite this

Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun / Ramsey numbers of trees versus fans.

In: Discrete mathematics, Vol. 338, No. 6, 06.2015, p. 994-999.

Research output: Scientific - peer-reviewArticle

@article{97be4a5f221842c6905fb9afd057d5f7,
title = "Ramsey numbers of trees versus fans",
abstract = "For two given graphs G1 and G2, the Ramsey number R(G1, G2) is the smallest integerN such that, for any graph G of order N, either G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn be a tree of order n, Sn a star of order n, and Fm a fan of order 2m + 1, i.e., m triangles sharing exactly one vertex. In this paper, we prove that R(Tn, Fm) = 2n − 1 for n ≥ 3m^2 − 2m − 1, and if Tn = Sn, then the range can be replaced by n ≥ max{m(m − 1) + 1, 6(m − 1)}, which is tight in some sense.",
keywords = "EWI-25790, MSC-05C, Tree, IR-94674, Star, Fan, METIS-312512, Ramsey number",
author = "Yanbo Zhang and Broersma, {Haitze J.} and Yaojun Chen",
note = "eemcs-eprint-25790",
year = "2015",
month = "6",
doi = "10.1016/j.disc.2015.01.030",
volume = "338",
pages = "994--999",
journal = "Discrete mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "6",

}

Zhang, Y, Broersma, HJ & Chen, Y 2015, 'Ramsey numbers of trees versus fans' Discrete mathematics, vol 338, no. 6, pp. 994-999. DOI: 10.1016/j.disc.2015.01.030

Ramsey numbers of trees versus fans. / Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun.

In: Discrete mathematics, Vol. 338, No. 6, 06.2015, p. 994-999.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - Ramsey numbers of trees versus fans

AU - Zhang,Yanbo

AU - Broersma,Haitze J.

AU - Chen,Yaojun

N1 - eemcs-eprint-25790

PY - 2015/6

Y1 - 2015/6

N2 - For two given graphs G1 and G2, the Ramsey number R(G1, G2) is the smallest integerN such that, for any graph G of order N, either G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn be a tree of order n, Sn a star of order n, and Fm a fan of order 2m + 1, i.e., m triangles sharing exactly one vertex. In this paper, we prove that R(Tn, Fm) = 2n − 1 for n ≥ 3m^2 − 2m − 1, and if Tn = Sn, then the range can be replaced by n ≥ max{m(m − 1) + 1, 6(m − 1)}, which is tight in some sense.

AB - For two given graphs G1 and G2, the Ramsey number R(G1, G2) is the smallest integerN such that, for any graph G of order N, either G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn be a tree of order n, Sn a star of order n, and Fm a fan of order 2m + 1, i.e., m triangles sharing exactly one vertex. In this paper, we prove that R(Tn, Fm) = 2n − 1 for n ≥ 3m^2 − 2m − 1, and if Tn = Sn, then the range can be replaced by n ≥ max{m(m − 1) + 1, 6(m − 1)}, which is tight in some sense.

KW - EWI-25790

KW - MSC-05C

KW - Tree

KW - IR-94674

KW - Star

KW - Fan

KW - METIS-312512

KW - Ramsey number

U2 - 10.1016/j.disc.2015.01.030

DO - 10.1016/j.disc.2015.01.030

M3 - Article

VL - 338

SP - 994

EP - 999

JO - Discrete mathematics

T2 - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 6

ER -

Zhang Y, Broersma HJ, Chen Y. Ramsey numbers of trees versus fans. Discrete mathematics. 2015 Jun;338(6):994-999. Available from, DOI: 10.1016/j.disc.2015.01.030