The Ramsey numbers of large trees versus wheels

Document Type : Research Paper

Authors

1 School of Economics and Management‎, ‎Southeast University‎, ‎Nanjing 210093‎, ‎P.R. China.

2 School of Management and Engineering‎, ‎Nanjing University‎, ‎Nanjing 210093‎, ‎P.R. China.

Abstract

For two given graphs $G_1$ and $G_2$, the Ramsey number $R(G_1,G_2)$ is the smallest integer n such that for any graph G of order n, either $G$ contains G1 or the complement of G contains $G_2$. Let Tn denote a tree of order n and Wm a wheel of order m+1. To the best of our knowledge, only $R(T_n,W_m)$ with small wheels are known. In this paper, we show that $R(T_n,W_m)=3n-2$ for odd m with $n>756m^{10}$.

Keywords

Main Subjects

References

J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, 244, Springer, New York, 2008.
E. T. Baskoro, Surahmat, S. M. Nababan and M. Miller, On Ramsey numbers for trees versus wheels of five or six vertices, Graphs Combin. 18 (2002), no. 4, 717--721.
S. A. Burr, P. Erdos, R. J. Faudree, C. C. Rousseau and R. H. Schelp, Ramsey numbers for the pair sparse graph-path or cycle, Trans. Amer. Math. Soc. 269 (1982), no. 2, 501--512.
Y. Chen, Y. Zhang and K. Zhang, The Ramsey numbersR(Tn;W6) for Δ(Tn) ≥n-3, Appl. Math. Lett. 17 (2004), no. 3, 281--285.
Y. Chen, Y. Zhang and K. Zhang, The Ramsey numbers of Trees versus W6 or W7, European J. Combin. 27 (2006), no. 4, 558--564.
Y. Chen, Y. Zhang and K. Zhang, The Ramsey numbersR(Tn;W6) for small n, Util. Math. 67 (2005) 269--284.
Y. Chen, Y. Zhang and K. Zhang, The Ramsey Numbers R(Tn;W6) for Tn without certain deletable sets, J. Syst. Sci. Complex 18 (2005), no. 1, 95--101.
S. P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2014), DS1.14.
Y. Zhang, Y. Chen and K. Zhang, The Ramsey numbers for trees of high degree versus a wheel of order nine, manuscript (2009).
Bulletin of the Iranian Mathematical Society
Volume 42, Issue 4 - Serial Number 4
August 2016
Pages 879-880

Files

History

  • Receive Date: 17 December 2014
  • Revise Date: 18 May 2015
  • Accept Date: 18 May 2015

Share

How to cite

Statistics