Ramsey Numbers of Stars Versus Generalised Wheels

doi:10.1007/s42967-023-00316-3

Communications on Applied Mathematics and Computation ›› 2025, Vol. 7 ›› Issue (4): 1333-1349.doi: 10.1007/s42967-023-00316-3

• ORIGINAL PAPERS • 上一篇下一篇

Ramsey Numbers of Stars Versus Generalised Wheels

Yiran Zhang, Yuejian Peng

School of Mathematics, Hunan University, Changsha, 410082, Hunan, China

收稿日期:2023-02-12 修回日期:2023-09-02 接受日期:2023-09-11 出版日期:2024-02-05 发布日期:2024-02-05
通讯作者: Yuejian Peng,E-mail:ypeng1@hnu.edu.cn E-mail:ypeng1@hnu.edu.cn
作者简介:Yiran Zhang, E-mail:zhangyiran1125@163.com
基金资助:
This work was supported by the NSFC (Grant no. 11931002).

Ramsey Numbers of Stars Versus Generalised Wheels

Yiran Zhang, Yuejian Peng

School of Mathematics, Hunan University, Changsha, 410082, Hunan, China

Received:2023-02-12 Revised:2023-09-02 Accepted:2023-09-11 Online:2024-02-05 Published:2024-02-05
Supported by:
This work was supported by the NSFC (Grant no. 11931002).

摘要/Abstract

摘要： 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.

关键词: Ramsey number, Star, Generalised wheel

Abstract: 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.

Key words: Ramsey number, Star, Generalised wheel

中图分类号:

05C35

Yiran Zhang, Yuejian Peng. Ramsey Numbers of Stars Versus Generalised Wheels[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1333-1349.

参考文献

[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 W₄ or W₅. 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)

Ramsey Numbers of Stars Versus Generalised Wheels

Ramsey Numbers of Stars Versus Generalised Wheels

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	Song Nie, Hua Dai. A Low-Rank Global Krylov Squared Smith Method for Solving Large-Scale Stein Matrix Equation[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 562-588.
[2]	Hongxing Wang, Pei Huang. Characterizations and Properties of Dual Matrix Star Orders[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 179-202.