On size multipartite Ramsey numbers for stars
Abstract
Burger and Vuuren defined the size multipartite Ramsey number for a pair of complete, balanced, multipartite graphs mj(Kaxb,Kcxd), for natural numbers a,b,c,d and j, where a,c >= 2, in 2004. They have also determined the necessary and sufficient conditions for the existence of size multipartite Ramsey numbers mj(Kaxb,Kcxd). Syafrizal et al. generalized this definition by removing the completeness requirement. For simple graphs G and H, they defined the size multipartite Ramsey number mj(G,H) as the smallest natural number t such that any red-blue coloring on the edges of Kjxt contains a red G or a blue H as a subgraph. In this paper, we determine the necessary and sufficient conditions for the existence of multipartite Ramsey numbers mj(G,H), where both G and H are non complete graphs. Furthermore, we determine the exact values of the size multipartite Ramsey numbers mj(K1,m, K1,n) for all integers m,n >= 1 and j = 2,3, where K1,m is a star of order m+1. In addition, we also determine the lower bound of m3(kK1,m, C3), where kK1,m is a disjoint union of k copies of a star K1,m and C3 is a cycle of order 3.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.19184/ijc.2019.3.2.4
References
AP. Burger and JH. van Vuuren, Ramsey numbers in complete balanced multipartite graphs Part II: Size Numbers, Discrete Math. 283 (2004), 45–49.
A. Lusiani, Syafrizal Sy, E.T. Baskoro, and C. Jayawardene, On size multipartite Ramsey numbers for stars versus cycles, Procedia Comput. Sci. 74 (2015), 27–31.
A. Lusiani, E.T. Baskoro, and S.W. Saputro, On size tripartite Ramsey numbers of P3 versus mK 1,n , AIP. Conf. Proc. 1707, 020010 (2016), doi:10.1063/1.4940811.
A. Lusiani, E.T. Baskoro, and S.W. Saputro, On size multipartite Ramsey numbers for stars versus paths and cycles, Electron. J. Graph Theory and Appl., 5 (1) (2017), 43–50.
A. Lusiani, E.T. Baskoro, and S.W. Saputro, On size multipartite Ramsey numbers of mK_1,n versus P_3 and K_1,3 , Proceedings of the Jangjeon Mathematical Society, 22 (1) (2019), 59–65, doi:10.17777/pjms2019.22.1.59.
C. Jayawardene and L. Samarasekara, A strict upper bound for size multipartite Ramsey numbers of paths versus stars, Indonesian J. Combin., 1 (2) (2017), 55–63.
Effendi, A.I. Baqi, and Syafrizal Sy, On size multipartite Ramsey numbers for paths versus stars, Int. J. Math. Analysis, 10 (2016), 1061–1065.
J.H. Hattingh and M.A. Henning, Star-Path bipartite Ramsey numbers, Discrete Math.185 (1998), 255–258.
Surahmat and Syafrizal Sy, Star-path size multipartite Ramsey numbers, Applied Math. Sci-ences (Bulgaria) 8 No.75 (2014), 3733–3736.
Syafrizal Sy, ET. Baskoro and S. Uttunggadewa, The size multipartite Ramsey number for paths, J. Combin. Math. Combin. Comput. 55 (2005), 103–107.
Syafrizal Sy, E.T. Baskoro, and S. Uttunggadewa, The size multipartite Ramsey numbers for small paths versus other graphs, Far East J. Appl. Math. 28 Issue 1 (2007), 131–138.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.