Ramsey Numbers of Stars Versus Generalised Wheels

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

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$S_{n}$$\end{document}

be a star of order n and

W_{s,m}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_{s,m}$$\end{document}

be a generalised wheel

K_s\vee C_m.

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$K_{s}\vee C_{m}.$$\end{document}

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}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_{s,4}$$\end{document}

-good,

W_{s,5}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_{s,5}$$\end{document}

-good,

W_{s,6}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_{s,6}$$\end{document}

-good, and

W_{s,7}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_{s,7}$$\end{document}

-good for

s⩾2.

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$s\geqslant 2.$$\end{document}

In this paper, we study the Ramsey numbers

R(S_n,W_{s,8}),

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$R(S_{n}, W_{s,8}),$$\end{document}

and our results indicate that trees are not always

W_{s,8}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_{s,8}$$\end{document}

-good.

Keywords

Ramsey number / Star / Generalised wheel

References

[1] BaskoroET, SurahmatS, NababanSM, MillerM. On Ramsey numbers for trees versus wheels of five or six vertices. Graphs Combin., 2002, 184717-721.

[2] BondyJA. Pancyclic graphs I. J. Combin. Theory Ser. B, 1971, 11180-84.

[3] BrandtS, FaudreeR, GoddardW. Weakly pancyclic graphs. J. Graph Theory, 1998, 273141-176.

[4] BurrSA. Ramsey numbers involving graphs with long suspended paths. J. Lond. Math. Soc., 1981, 243405-413.

[5] ChenY, ZhangY, ZhangK. The Ramsey numbers of stars versus wheels. Eur. J. Combin., 2004, 2571067-1075.

[6] ChngZ, TanT, WongK. On the Ramsey numbers for the tree graphs versus certain generalised wheel graphs. Discret. Math., 2021, 3448. 112440

[7] DiracGA. Some theorems on abstract graphs. Proc. Lond. Math. Soc., 1952, 2: 69-81.

[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] HasmawatiE, BaskoroT, AssiyatunH. Star-wheel Ramsey numbers. J. Comb. Math. Combin. Comput., 2005, 55: 123-128

[11] LiB, SchiermeyerI. On star-wheel Ramsey numbers. Graphs Combin., 2016, 322733-739.

[12] LinQ, LiY, DongL. Ramsey goodness and generalized stars. Eur. J. Combin., 2010, 3151228-1234.

[13] Surahmat, S., Baskoro, E.T.: On the Ramsey number of a path or a star versus W4\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_4$$\end{document} or W5\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_5$$\end{document}. In: Proceedings of the 12-th Australasian Workshop on Combinatorial Algorithms (Bandung, Indonesia), July 14–17, pp. 174–178 (2001)

[14] WangL, ChenY. The Ramsey numbers of trees versus generalized wheels. Graphs Combin., 2019, 351189-193.

[15] ZhangY, ChenY, ZhangK. The Ramsey numbers for stars of even order versus a wheel of order nine. Eur. J. Combin., 2005, 2971744-1754.

[16] ZhangY, ChengTCE, ChenY. The Ramsey numbers for stars of odd order versus a wheel of order nine. Discret. Math. Algorithms Appl., 2009, 13413-436.

Funding

National Natural Science Foundation of China(NO. 11931002)

RIGHTS & PERMISSIONS

Shanghai University