On the Ramsey Minimal Graphs for Matching and Disjoint Union of Complete Bipartite Graphs

Muhammad Rafif Fajri, Lyra Yulianti, Des Welyyanti

Abstract


Let G and H be two arbitrary graphs. The notation F -> (G,H) means that any red-blue coloring of every edge of F always resulting a red subgraph containing G  or a blue subgraph containing H. Denote F*:= F \ {e} for any edge of F. The notation F*/-> means that there exists a coloring of F* such that F* does not contain red G and blue H. The class R(G,H) states a set of graphs satisfying: (1) F -> (G,H) (2) For every edge e in F, F*:= F \ {e} /-> (G,H). In this paper, some graphs in R(aK_2, bK_3,n) are obtained, where aK_2 is a matching and bK_3,n  is a disjoint union of complete bipartite graphs K_3,n  for positive integer n.

Keywords


Ramsey minimal graph; Matching; Complete bipartite graph

Full Text:

PDF

References


Baskoro, E.T., Wijaya, K. 2015. On Ramsey (2K_2,K_4)-minimal graphs. In: Mathematics in the 21st Century, Springer Proceedings in Mathematics & Statistics Vol. 98: 11 – 17

Baskoro, E.T., Yulianti, L. 2011. On Ramsey minimal graphs for 2K_2 versus P_n. Adv. Appl. Discrete Math. 8(2): 83 – 90

Burr, S. A., Erdős, P., Lovasz, L. 1976. On Graph of Ramsey Type, Ars Combinatoria: 167 – 190.

Burr, S.A., Erdös, P., Faudree, R.J., Schelp, R.H. 1978. A class of Ramsey-finite graphs. In: Proceeding of the Ninth Southeastern Conference on Combinatorics, Graph Theory and Computing: 171 – 180

Burr, S.A., Erdös, P., Faudree, R.J., Schelp, R.H.: 1981. Ramsey minimal graphs for matchings. In: The Theory and Applications of Graphs (Kalamazoo, Mich.): 159 – 168

Burr, S.A., Erdös, P., Faudree, R.J., Rousseau, C.C., Schelp, R.H. 1982. Ramsey minimal graphs for forests. Discrete Math. 38(1): 23 – 32

Diestel, R., 2017, Graph Theory, 5^th ed., Springer-Verlag New York Inc., New York

Fajri, M. R., Yulianti, L., Welyyanti, D., 2022. Ramsey Minimal Graph for Union of Complete Graph and Complete Bipartite Graph, submitted to Electronic Journal of Graph Theory and Applications

Fitriani D., Salman A.N.M. 2016. Rainbow connection number of amalgamation of some graph. AKCE Internasional Journal of Graph and Combinatorics 13: 90 –99

Mengersen, I., Oeckermann, J. 1999. Matching-star Ramsey sets. Discrete Appl. Math. 95: 417 – 424

Muhshi, H., Baskoro, E.T. 2012. On Ramsey (3K_2,P_3)-minimal graphs. AIP Conference Proceeding 1450: 110 – 117

Nabila, M., Yulianti, L., Syafwan, M., 2019. Graf Ramsey Minimal Untuk Pasangan Gabungan Graf Lengkap K_2 dan Gabungan Graf Bintang K_(1,n) (in Bahasa), Jurnal Matematika UNAND. 8(1): 195 – 200

Wijaya, K. , Baskoro, E. T. 2016. On Ramsey (2K_2,2H)-Minimal Graphs, Springer India, J. Math, 186: 219 – 223

Wijaya, K., Baskoro, E.T., Assiyatun, H., Suprijanto, D. 2016. On Ramsey (3K_2,K_3)-minimal graphs. In: AIP Conference Proceedings Vol. 1707, pp. 020025. doi:10.1063/1.4940826

Wijaya, K., Baskoro, E.T., Assiyatun, H., Suprijanto, D. 2016. On Ramsey (mK_2,H)-Minimal Graphs, Graphs and Combinatorics Vol. 23: 233 – 243

Wijaya, K., Baskoro, E.T., Assiyatun, H., Suprijanto, D. 2018, On Ramsey (4K_2,P_3)-minimal graphs, AKCE International Journal of Graphs and Combinatorics 15(2): 174 – 186

Wijaya, K., Baskoro, E.T., Assiyatun, H., Suprijanto, D. 2015. On unicyclic Ramsey (mK_2,P_3)-minimal graphs. Proc. Comput. Sci. 74: 10 – 14

Wijaya, K., Baskoro, E.T., Assiyatun, H., Suprijanto, D., 2020, Subdivision of graphs in R(mK_2,P_4), Heliyon 6(6): e03843

Wijaya, K., Baskoro, E.T., Assiyatun, H., Suprijanto, D. 2015. The complete list of Ramsey (2K_2,K_4)-minimal graphs. Electron. J. Graph Theory Appl. 3(2) : 216 – 227

Wijaya, K., Yulianti, L., Baskoro, E.T., Assiyatun, H., Suprijanto, D. 2015. All Ramsey (2K_2,C_4)-minimal graphs. J. Algorithms Comput. 46: 9 – 25




DOI: http://dx.doi.org/10.52155/ijpsat.v36.1.4849

Refbacks

  • There are currently no refbacks.


Copyright (c) 2022 Muhammad Rafif Fajri, Lyra Yulianti, Des Welyyanti

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.