Abstract
For two given graphs G and H, the Ramsey number R(G, H) is the smallest positive integer N such that for every graph F of order N the following holds: either F contains G as a subgraph or the complement of F contains H as a subgraph. In this paper, we shall study the Ramsey number R(Tn, Wn) for a star-like tree Tn with n vertices and a wheel Wm with m + 1 vertices and m odd. We show that the Ramsey number R(Sn, Wm) = 3n - 2 for n ≥ 2m - 4, m ≥ 5 and m odd, where Sn denotes the star on n vertices. We conjecture that the Ramsey number is the same for general trees on n vertices, and support this conjecture by proving it for a number of star-like trees.
| Original language | English |
|---|---|
| Pages (from-to) | 153-162 |
| Number of pages | 10 |
| Journal | Journal of Combinatorial Mathematics and Combinatorial Computing |
| Volume | 65 |
| Publication status | Published - May 2008 |
Keywords
- Ramsey number
- Star
- Tree
- Wheel