Ramsey minimal graphs for a pair of a cycle on four vertices and an arbitrary star

Maya Nabila, Hilda Assiyatun, Edy Tri Baskoro

Abstract


Let F, G and H be simple graphs. The notation F → (G, H) means that for any red-blue coloring on the edges of graph F, there exists either a red copy of G or a blue copy of H. A graph F is called a Ramsey (G, H)-minimal graph if it satisfies two conditions: (i) F → (G, H) and (ii) F − e ↛ (G, H) for any edge e of F. In this paper, we give some finite and infinite classes of Ramsey (C4, K1, n)-minimal graphs for any n ≥ 3.


Keywords


Ramsey minimal graph, cycle, star

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2022.10.1.20

References

E.T. Baskoro, L. Yulianti, and H. Assiyatun. Ramsey (K1, 2, C4)-minimal graphs, J. Combin. Math. Combin. Comput., 65 (2008), 79–90.

S.A. Burr, P. Erds, R.J. Faudree, and R. H. Schelp, A class of Ramsey-finite graphs, In Proc. 9th SE Conf. on Combinatorics, Graph Theory and Computing, (1978), 171–178.

S.A. Burr, P. Erds, and L. Lovász, On graphs of Ramsey type. Ars Combinatoria, 1(1) (1976), 167–190.

F.F. Hadiputra and D.R. Silaban, Infinite family of Ramsey (K1, 2, C4)-minimal graphs. Journal of Physics: Conference Series, 1722 (1) (2020), 012049.

K. Wijaya, E.T. Baskoro, H. Assiyatun, and D. Suprijanto, The complete list of Ramsey (2K2, K4)-minimal graphs. Electronic Journal of Graph Theory and Applications (EJGTA), 3 (2) (2015), 216–227.

H. Muhshi and E.T. Baskoro, Matching-star Ramsey minimal graphs. Mathematics in Computer Science, 9 (4) (2015), 443–452.

J. Nešetřil and Rdl, The structure of critical Ramsey graphs. Acta Mathematica Hungarica, 32 (3-4) (1978), 295–300.

M. Nabila and E.T. Baskoro, On Ramsey (Cn, H)-minimal graphs. In Journal of Physics: Conference Series, 1722 (1) (2021), 012052.

F. Nisa, D. Rahmadani, Purwanto, and H. Susanto, On Ramsey (P3, C6)-minimal graphs. AIP Conference Proceedings, 2215 (1) (2020), 070010.

M. Nabila, E.T. Baskoro, and H. Assiyatun, Ramsey graphs for a star on three vertices versus a cycle. In International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC): Atlantis Press, (2022), 5–10.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

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

View EJGTA Stats