The Ramsey numbers of large star and large star-like trees versus odd wheels

  • Cak Surahmat*
  • , Edy Tri Baskoro
  • , H. J. Broersma
  • *Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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 languageEnglish
Pages (from-to)153-162
Number of pages10
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
Volume65
Publication statusPublished - May 2008

Keywords

  • Ramsey number
  • Star
  • Tree
  • Wheel

Fingerprint

Dive into the research topics of 'The Ramsey numbers of large star and large star-like trees versus odd wheels'. Together they form a unique fingerprint.

Cite this