Ramsey numbers of trees versus fans

Yanbo Zhang, Haitze J. Broersma, Yaojun Chen

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
19 Downloads (Pure)

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
Publication statusPublished - Jun 2015

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. 2015 ; Vol. 338, No. 6. pp. 994-999.
@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",
language = "Undefined",
volume = "338",
pages = "994--999",
journal = "Discrete mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "6",

}

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

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

JF - Discrete mathematics

SN - 0012-365X

IS - 6

ER -