On Ramsey (C4, K1, n)-minimal graphs

Hilda Assiyatun, Maya Nabila, Edy Tri Baskoro

Abstract


Let F, G and H be any simple graphs. The notation F → (G, H) means 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. If F → (G, H), then graph F is called a Ramsey graph for (G, H). Additionally, if the graph F satisfies that F − e ↛ (G, H) for any edge e of F, then graph F is called a Ramsey (G, H)-minimal. The set of all Ramsey (G, H)-minimal graphs is denoted by ℛ(G, H). In this paper, we construct a new class of Ramsey (C4, K1, n)-minimal graphs.

 

Keywords


Ramsey minimal graph; cycle; star

Full Text:

PDF

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

References

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

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, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, Ramsey minimal graphs for the pair star-connected graph, Studia Sci. Math. Hungar. 15 (1980), 265–273.

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

M. Borowiecki, I. Schiermeyer and E. Sidorowicz, Ramsey (K1, 2, K3)-minimal Graphs, Electron. J. Combin. 12 (2005), #R20.

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

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

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

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.

M. Nabila, H. Assiyatun and E.T. Baskoro, Ramsey minimal graphs for a pair of a cycle on four vertices and an arbitrary star, Electron. J. Graph Theory Appl. 10(1) (2022), 289–299.


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