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 | English |
|---|---|
| Pages (from-to) | 994-999 |
| Number of pages | 6 |
| Journal | Discrete mathematics |
| Volume | 338 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - Jun 2015 |
Keywords
- Tree
- Star
- Fan
- Ramsey number
- 22/4 OA procedure
Fingerprint
Dive into the research topics of 'Ramsey numbers of trees versus fans'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver