On Ramsey numbers for trees versus fans of even order
Abstract
Given two graphs G and H. The graph Ramsey number R(G, H) is the least natural number r such that for every graph F on r vertices, either F contains a copy of G or F̅ contains a copy of H. A vertex v is called a dominating vertex in a graph G if it is adjacent to all other vertices of G. A wheel Wm is a graph consisting one dominating vertex and m other vertices forming a cycle. A fan graph F1,m is a graph formed from a wheel Wm by removing one cycle-edge. In this paper, we consider the graph Ramsey number R(Tn,F1,m) of a tree Tn versus a fan F1,m. The study of R(Tn,F1,m) has been initiated by Li et. al. (2016) where Tn is a star, and continued by Sherlin et. al. (2023) for Tn which is not a star and fan F1,m with even m ≤ 8. This paper will give the graph Ramsey numbers R(Tn,F1,m) for odd m ≤ 8.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.19184/ijc.2024.8.1.2
References
E.T. Baskoro, Surahmat, S.M. Nababan and M. Miller, On Ramsey number for tree versus wheel of five and six vertices, Graphs Combin., 18 (2002), 717--721.
J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, (2008).
A. Bondy, Pancyclic graphs, J. Combin. Theory, Ser. B, 11 (1971), 80--84.
Y.J. Chen, Y.Q. Zhang and K.M. Zhang, The Ramsey number R(Tn,W6) for Δ(Tn) ≥ n-3, Appl. Math. Lett., 17 (2004), 281--285.
Y.J. Chen, Y.Q. Zhang and K.M. Zhang, The Ramsey number R(Tn,W6) for small n, Util. Math., 67 (2005).
Y.J. Chen, Y.Q. Zhang and K.M. Zhang, The Ramsey number R(Tn,W6) for Tn without certain deletable sets, J. Syst. Sci. Compl., 18 (2005), 95-101.
Y.J. Chen, Y.Q. Zhang and K.M. Zhang, The Ramsey numbers of stars versus wheels, European J. Combin., 25 (2004), 1067--1075.
Y.J. Chen, Y.Q. Zhang and K.M. Zhang, The Ramsey numbers of trees versus W6 or W7, European J. Combin., 27 (2006), 558-564.
V. Chv'{a}tal and F. Harary, Generalized Ramsey theory for graphs, III: Small off-diagonal numbers, Pacific J. Math., 41 (1972), 335--345.
Yusuf Hafidh, Edy Tri Baskoro, The Ramsey number for tree versus wheel with odd order, Bull. Malays. Math. Soc., 44 (4) (2021), 2151--2160.
Hasmawati, E.T. Baskoro and H. Assiyatun, Star-wheel Ramsey numbers, J. Combin. Math. Combin. Comput., 55 (2005), 123--128.
Surahmat and E.T. Baskoro, On the Ramsey number of a path or a star versus W4 or W5, Proceeding of the 12th Australian Workshop on Combinatorial Algorithms, Bandung, Indonesia, July 14-17 (2001), 174--179.
Surahmat, E.T. Baskoro and H.J. Broersma, The Ramsey numbers of large stars-like trees versus large odd wheels, J. Combin. Math. Combin. Comput., 65 (2008), 153--162.
Y. Zhang, H. Broersma and Y. Chen, A remark on star-C4 and wheel-C4 Ramsey numbers, Electron. J. Graph Theory Appl., 2 (2) (2014), 110--114.
Y.Q. Zhang, H. Broersma and Y.J. Chen, On fan-wheel and tree-wheel Ramsey numbers, Discrete Math., 339 (2016), 2284--2287.
Y. Zhang and Y. Chen, The Ramsey numbers of fans versus a complete graph of order five, Electron. J. Graph Theory Appl., 2 (1) (2014), 66--69.
Y.Q. Zhang, Y.J. Chen and K. Zhang, The Ramsey number for stars of even order versus a wheel of order nine, European J. Combin., 29 (2008), 1744--1754.
Y.Q. Zhang, T.C.E. Cheng and Y.J. Chen, The Ramsey number for stars of odd order versus a wheel of order nine, Discrete Math. Algorithms Appl., 1 (2009), 413--436.
B. Li, Y.Q. Zhang, H. Broersma, An exact formula for all star-kipas Ramsey numbers, Graphs Combin., 33 (2017), 141--148.
I. Sherlin, S.W. Saputro, E.T. Baskoro, On Ramsey number for tree versus fan graph of odd order, Proceeding of ICMNS 2023, accepted.
L. Gerencser and A. Gyarfas, On Ramsey-type problems, Ann. Univ. Sci. Budapest. Eotvos Sect. Math., 10 (1967), 167--170.
S. A. Burr, Ramsey numbers involving graphs with long suspended paths, J. the London Math. Soc., 2.3 (1981), 405-413.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.