For two graphs $G$ and $H$, the Ramsey number $R(G, H)$ is the smallest integer $n$ such that for any $n$-vertex graph, either it contains $G$ or its complement contains $H$. Let $S_n$ be a star of order $n$ and $W_{s, m}$ be a generalised wheel $K_s \vee C_m$. Previous studies by Wang and Chen (Graphs Comb 35(1):189-193, 2019) and Chng et al. (Discret Math 344(8):112440, 2021) imply that a tree is $W_{s, 4^{-}}$good, $W_{s, 5^{-}}$good, $W_{s, 6}$-good, and $W_{s, 7^{-}}$good for $s \geqslant 2$. In this paper, we study the Ramsey numbers $R\left(S_n, W_{s, 8}\right)$, and our results indicate that trees are not always $W_{s, 8}$-good.
Yiran Zhang
,
Yuejian Peng
. Ramsey Numbers of Stars Versus Generalised Wheels[J]. Communications on Applied Mathematics and Computation, 2025
, 7(4)
: 1333
-1349
.
DOI: 10.1007/s42967-023-00316-3
[1] Baskoro, E.T., Surahmat, S., Nababan, S.M., Miller, M.: On Ramsey numbers for trees versus wheels of five or six vertices. Graphs Combin. 18(4), 717-721 (2002)
[2] Bondy, J.A.: Pancyclic graphs I. J. Combin. Theory Ser. B 11(1), 80-84 (1971)
[3] Brandt, S., Faudree, R., Goddard, W.: Weakly pancyclic graphs. J. Graph Theory 27(3), 141-176 (1998)
[4] Burr, S.A.: Ramsey numbers involving graphs with long suspended paths. J. Lond. Math. Soc. 24(3), 405-413 (1981)
[5] Chen, Y., Zhang, Y., Zhang, K.: The Ramsey numbers of stars versus wheels. Eur. J. Combin. 25(7), 1067-1075 (2004)
[6] Chng, Z., Tan, T., Wong, K.: On the Ramsey numbers for the tree graphs versus certain generalised wheel graphs. Discret. Math. 344(8), 112440 (2021)
[7] Dirac, G.A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. 2, 69-81 (1952)
[8] Hajnal, A., Szemerédi, E.: Proof of a conjecture of P. Erdős. In: Combinatorial Theory and Its Applications, II (Proc. Colloq., Balatonfured, 1969), pp. 601-623 (1970)
[9] Hasmawati, E.: Bilangan Ramsey: untuk kombinasi Graf Bintang terhadap Graf Roda. Tesis Magister, Departemen Matematika ITB, Indonesia (2004)
[10] Hasmawati, E., Baskoro, T., Assiyatun, H.: Star-wheel Ramsey numbers. J. Comb. Math. Combin. Comput. 55, 123-128 (2005)
[11] Li, B., Schiermeyer, I.: On star-wheel Ramsey numbers. Graphs Combin. 32(2), 733-739 (2016)
[12] Lin, Q., Li, Y., Dong, L.: Ramsey goodness and generalized stars. Eur. J. Combin. 31(5), 1228-1234 (2010)
[13] Surahmat, S., Baskoro, E.T.: On the Ramsey number of a path or a star versus W4 or W5. In: Proceedings of the 12-th Australasian Workshop on Combinatorial Algorithms (Bandung, Indonesia), July 14-17, pp. 174-178 (2001)
[14] Wang, L., Chen, Y.: The Ramsey numbers of trees versus generalized wheels. Graphs Combin. 35(1), 189-193 (2019)
[15] Zhang, Y., Chen, Y., Zhang, K.: The Ramsey numbers for stars of even order versus a wheel of order nine. Eur. J. Combin. 29(7), 1744-1754 (2005)
[16] Zhang, Y., Cheng, T.C.E., Chen, Y.: The Ramsey numbers for stars of odd order versus a wheel of order nine. Discret. Math. Algorithms Appl. 1(3), 413-436 (2009)
