The Ramsey numbers for trees of large maximum degree versus the wheel graph \(W_8\). (English) Zbl 07896531
Summary: The Ramsey numbers \(R(T_n, W_8)\) are determined for each tree graph \(T_n\) of order \(n \geq 7\) and maximum degree \(\Delta (T_n)\) equal to either \(n-4\) or \(n-5\). These numbers indicate strong support for the conjecture, due to Y. Chen et al. [Appl. Math. Lett. 17, No. 3, 281–285 (2004; Zbl 1055.05104)] and to Y. Hafidh and E. T. Baskoro [Bull. Malays. Math. Sci. Soc. (2) 44, No. 4, 2151–2160 (2021; Zbl 1470.05111)], that \(R(T_n, W_m) = 2n-1\) for each tree graph \(T_n\) of order \(n \geq m-1\) with \(\Delta (T_n) \leq n-m+2\) when \(m \geq 4\) is even.
MSC:
| 05C55 | Generalized Ramsey theory |
| 05D10 | Ramsey theory |
| 05C07 | Vertex degrees |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Baskoro, ET, The Ramsey number of paths and small wheels, Majalah Ilmiah Himpunan Matematika Indonesia, 8, 13-16, 2002 |
| [2] | Baskoro, ET; Surahmat, Surahmat The Ramsey number of paths with respect to wheels, Discrete Math., 294, 275-277, 2005 · Zbl 1062.05097 · doi:10.1016/j.disc.2004.10.024 |
| [3] | Baskoro, ET; Surahmat; Nababan, SM; Miller, M., On Ramsey graph numbers for trees versus wheels of five or six vertices, Graphs Combin., 18, 717-721, 2002 · Zbl 1009.05098 · doi:10.1007/s003730200056 |
| [4] | Bondy, JA, Pancyclic graphs, J. Comb. Theory Ser. B, 11, 80-84, 1971 · Zbl 0183.52301 · doi:10.1016/0095-8956(71)90016-5 |
| [5] | Burr, SA; Erdős, P.; Faudree, RJ; Rousseau, CC; Schelp, RH; Gould, RJ; Jacobson, MS, Goodness of trees for generalized books, Graphs Comb., 3, 1-6, 1987 · Zbl 0612.05046 · doi:10.1007/BF01788524 |
| [6] | Chartrand, G.; Lesniak, L.; Zhang, P., Graphs and Digraphs, 2015, Boston: Chapman and Hall/CRC, Boston · doi:10.1201/b19731 |
| [7] | Chvátal, V.; Harary, F., Generalized Ramsey theory for graphs, III: small off-diagonal numbers, Pac. J. Math., 41, 335-345, 1972 · Zbl 0227.05115 · doi:10.2140/pjm.1972.41.335 |
| [8] | Chen, Y.; Zhang, Y.; Zhang, K., The Ramsey numbers of stars versus wheels, Eur. J. Comb., 25, 1067-1075, 2004 · Zbl 1050.05087 · doi:10.1016/j.ejc.2003.12.004 |
| [9] | Chen, Y.; Zhang, Y.; Zhang, K., The Ramsey numbers \(R(T_n, W_6)\) for \(\Delta (T_n)\ge n-3\), Appl. Math. Lett., 17, 281-285, 2004 · Zbl 1055.05104 · doi:10.1016/S0893-9659(04)90064-X |
| [10] | Chen, Y.; Zhang, Y.; Zhang, K., The Ramsey numbers \(R(T_n, W_6)\) for small \(n\), Util. Math., 67, 269-284, 2005 · Zbl 1068.05067 |
| [11] | Chen, Y.; Zhang, Y.; Zhang, K., The Ramsey numbers \(R(T_n, W_6)\) for \(T_n\) without certain deletable sets, J. Syst. Sci. Complex, 18, 95-101, 2005 · Zbl 1120.05058 |
| [12] | Chen, Y.; Zhang, Y.; Zhang, K., The Ramsey numbers of paths versus wheels, Discrete Math., 290, 85-87, 2005 · Zbl 1059.05074 · doi:10.1016/j.disc.2004.10.017 |
| [13] | Chen, Y.; Zhang, Y.; Zhang, K., The Ramsey numbers of trees versus \(W_6\) or \(W_7\), Eur. J. Comb., 27, 558-564, 2006 · Zbl 1098.05053 · doi:10.1016/j.ejc.2004.12.003 |
| [14] | Hafidh, Y.; Baskoro, ET, The Ramsey number for tree versus wheel with odd order, Bull. Malays. Math. Sci. Soc., 44, 2151-2160, 2021 · Zbl 1470.05111 · doi:10.1007/s40840-020-01055-x |
| [15] | Haghi, Sh; Maimani, HR, A note on the Ramsey number of even wheels versus stars, Discuss. Math. Graph Theory, 38, 397-404, 2018 · Zbl 1390.05140 · doi:10.7151/dmgt.2009 |
| [16] | Hasmawati, H.; Baskoro, ET; Assiyatun, H., Star-wheel Ramsey numbers, J. Comb. Math. Comb. Comput., 55, 123-128, 2005 · Zbl 1100.05065 |
| [17] | Jackson, B., Cycles in bipartite graphs, J. Comb. Theory Ser. B, 30, 332-342, 1981 · Zbl 0468.05048 · doi:10.1016/0095-8956(81)90050-2 |
| [18] | Korolova, A., Ramsey numbers of stars versus wheels of similar sizes, Discrete Math., 292, 107-117, 2005 · Zbl 1062.05098 · doi:10.1016/j.disc.2004.12.003 |
| [19] | Li, B.; Ning, B., The Ramsey numbers of paths versus wheels: a complete solution, Electron. J. Combin., 21, 4, #P4.41, 2014 · Zbl 1305.05140 · doi:10.37236/3968 |
| [20] | Li, B.; Schiermeyer, I., On star-wheel Ramsey numbers, Graphs Comb., 32, 733-739, 2016 · Zbl 1338.05178 · doi:10.1007/s00373-015-1594-6 |
| [21] | Salman, ANM; Broersma, HJ, The Ramsey Numbers for paths versus wheels, Discrete Math., 307, 975-982, 2007 · Zbl 1115.05060 · doi:10.1016/j.disc.2005.11.049 |
| [22] | Surahmat, Baskoro, E.T.: 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, 14-17 July 2001, pp. 165-170 (2001) |
| [23] | Zhang, Y., On Ramsey numbers of short paths versus large wheels, Ars Comb., 89, 11-20, 2008 · Zbl 1224.05346 |
| [24] | Zhang, Y., The Ramsey numbers for stars of odd small order versus a wheel of order nine, Nanjing Daxue Xuebao Shuxue Bannian Kan, 25, 35-40, 2008 · Zbl 1174.05084 |
| [25] | Zhang, Y.; Chen, Y.; Zhang, K., The Ramsey numbers for stars of even order versus a wheel of order nine, Eur. J. Comb., 29, 1744-1754, 2008 · Zbl 1161.05049 · doi:10.1016/j.ejc.2007.07.005 |
| [26] | Zhang, Y.; Cheng, TCE; Chen, Y., The Ramsey numbers for stars of odd order versus a wheel of order nine, Discrete Math. Algorithms Appl., 1, 413-436, 2009 · Zbl 1223.05188 · doi:10.1142/S1793830909000336 |
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.
