# Ramsey numbers of trees versus fans

Yanbo Zhang, Haitze J. Broersma, Yaojun Chen

2 Citations (Scopus)

### 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 language Undefined 994-999 6 Discrete mathematics 338 6 https://doi.org/10.1016/j.disc.2015.01.030 Published - Jun 2015

### Keywords

• Tree
• Star
• Fan
• 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 = "Tree, Star, Fan, Ramsey number",
author = "Yanbo Zhang and Broersma, {Haitze J.} and Yaojun Chen",
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.

TY - JOUR

T1 - Ramsey numbers of trees versus fans

AU - Zhang, Yanbo

AU - Broersma, Haitze J.

AU - Chen, Yaojun

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

KW - Star

KW - Fan

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 -