A note on the Ramsey number of even wheels versus stars. (English) Zbl 1390.05140
Summary: For two graphs \(G_1\) and \(G_2\), the Ramsey number \(R(G_1,G_2)\) is the smallest integer \(N\), such that for any graph on \(N\) vertices, either \(G\) contains \(G_1\) or \(\overline G\) contains \(G_2\). Let \(S_n\) be a star of order \(n\) and \(W_m\) be a wheel of order \(m + 1\). In this paper, we will show \(R(W_n, S_n)\leq 5n/2 - 1\), where \(n\geq6\) is even. Also, by using this theorem, we conclude that \(R(W_n, S_n) = 5n/2 - 2\) or \(5n/2 -1\), for \(n\geq6\) and even. Finally, we prove that for sufficiently large even \(n\) we have \(R(W_n, S_n) = 5n/2 - 2\).
References:
| [1] | S. Brandt, R. Faudree and W. Goddard, Weakly pancyclic graphs, J. Graph Theory 27 (1998) 141-176. doi:10.1002/(SICI)1097-0118(199803)27:3h141::AID-JGT3i3.0.CO;2-O; · Zbl 0927.05045 |
| [2] | G. Chartrand and O.R. Oellermann, Applied and Algorithmic Graph Theory (Mc Graw-Hill Inc, 1993).; |
| [3] | Y. Chen, Y. Zhang and K. Zhang, The Ramsey numbers of stars versus wheels, European J. Combin. 25 (2004) 1067-1075. doi:10.1016/j.ejc.2003.12.004; · Zbl 1050.05087 |
| [4] | V. Chvátal and F. Harary, Generalized Ramsey theory for graphs, III. Small offdiagonal numbers, Pac. J. Math. 41 (1972) 335-345. doi:10.2140/pjm.1972.41.335; · Zbl 0227.05115 |
| [5] | G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. 2 (1952) 69-81. doi:10.1112/plms/s3-2.1.69; · Zbl 0047.17001 |
| [6] | R.J. Faudree and R.H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974) 313-329. doi:10.1016/0012-365X(74)90151-4; · Zbl 0294.05122 |
| [7] | J.M. Hasmawati, Bilangan Ramsey untuk Graf Bintang Terhadap Graf Roda (Tesis Magister, Departemen Matematika ITB, Indonesia, 2004).; |
| [8] | E.T. Hasmawati, E.T. Baskoro and H. Assiyatun, Star-wheel Ramsey numbers, J. Combin. Math. Combin. Comput. 55 (2005) 123-128.; · Zbl 1100.05065 |
| [9] | A. Korolova, Ramsey numbers of stars versus wheels of similar sizes, Discrete Math. 292 (2005) 107-117. doi:10.1016/j.disc.2004.12.003; · Zbl 1062.05098 |
| [10] | B. Li and I. Schiermeyer, On star-wheel Ramsey numbers, Graphs Combin. 32 (2016) 733-739. doi:10.1007/s00373-015-1594-6; · Zbl 1338.05178 |
| [11] | V. Rosta, On a Ramsey-type problem of J.A. Bondy and P. Erdös, II, J. Combin. Theory Ser. B 15 (1973) 105-120. doi:10.1016/0095-8956(73)90036-1; · Zbl 0261.05119 |
| [12] | Surahmat and E.T. Baskoro, On the Ramsey number of a path or a star versus \(W_4\) or \(W_5\), in: Proceedings of the 12th Australasian Workshop on Combinatorial Algorithms (Bandung, Indonesia, July, 2001) 174-179.; |
| [13] | Y. Zhang, T.C.E. Cheng and Y. Chen, The Ramsey numbers for stars of odd order versus a wheel of order nine, Discrete Math. Algorithms Appl. 1 (2009) 413-436. doi:10.1142/S1793830909000336; · Zbl 1223.05188 |
| [14] | Y. Zhang, Y. Chen and K. Zhang, The Ramsey numbers for stars of even order versus a wheel of order nine, European J. Combin. 29 (2008) 1744-1754. doi:10.1016/j.ejc.2007.07.005; · Zbl 1161.05049 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
