On Ramsey (2K2, Wn)-minimal graphs of smallest order

Muhammad Rafif Fajri, Hilda Assiyatun, Edy Tri Baskoro

Abstract


The notation F → (H, G) means that if all edges of F are arbitrarily colored by red or blue, then either the subgraph of F induced by all red edges contains a graph H or the subgraph of F induced by all blue edges contains a graph G. Let R(H, G) denote the set of all graphs F satisfying F → (H, G) and for every e ∈ E(F), (F − e) ↛ (H, G). In this paper, we propose some properties of Ramsey (2K2, G)-minimal graph of smallest order, where G is a graph containing a dominating vertex. We also find all members of R(2K2, Wn) of smallest order for n ∈ [5,8].

Keywords


dominating vertex; matching; ramsey minimal graph; wheel

Full Text:

PDF

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

References

Assiyatun, H., Nabila, M., and Baskoro, E.T. On Ramsey (C4, K1,n)-minimal graphs. Electron. J. Graph Theory Appl. 11 (1) (2022), 149–154.

Baskoro, E.T. and Wijaya, K. On Ramsey (2K2, K4)-minimal graphs. Mathematics in the 21st Century, Springer Proc. Math. Stat. 98 (2015), 11–17.

Baskoro, E.T., Wijaya, K., and Ryan, J. All unicyclic Ramsey (mK2, P4)-minimal graphs. Australas. J. Combin. 82 (3) (2022), 237–255.

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

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

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

Erdős, P. and Rado, R. Combinatorial theorems on classifications of subsets of a given set. Proc. Lond. Math. Soc. 3 (2) (1952), 417–439.

Faudree, R.J., Schelp, R.H., and Sheehan, J. Ramsey number for matchings. Discrete Math. 32 (1980), 105–123.

Fajri, M.R., Assiyatun, H., and Baskoro, E.T. Characterization of R(2K2, Fn) with Minimum Order for Small n. J. Indones. Math. Soc. 31 (2) (2025), 1–19.

Łuczak, T. On Ramsey minimal graphs. The Electron. J. Combin. 1 (1994), #R4.

Mengersen, I. and Oeckermann, J. Matching-star Ramsey Sets. Discrete Appl. Math. 95 (1999), 417–424.

Muhshi, H. and Baskoro, E.T. On Ramsey (3K2, P3)-minimal graphs. AIP Conf. Proc. 1450 (2012), 110–117.

Nabila, M., Assiyatun, H., and Baskoro, E.T. 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.

Ramsey, F.P. On a problem of formal logic. Proc. Lond. Math. Soc. 30 (1930), 264–286.

Sudarsana, I.W. A note on the Ramsey number for a cycle with respect to a disjoint union of wheels. Electron. J. Graph Theory Appl. 9 (2) (2021), 561–566.

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

Wijaya, K., Baskoro, E.T., Assiyatun, H., and Suprijanto, D. On Unicyclic Ramsey (mK2, P3)-minimal graphs. Procedia Computer Science 74 (2015), 10–14.

Wijaya, K., Baskoro, E.T., Assiyatun, H., and Suprijanto, D. On Ramsey (mK2, H)-Minimal Graphs. Graphs Comb. 23 (2017), 233–243.

Yulianti, L., Assiyatun, H., Utunggadewa, S., and Baskoro, E.T. On Ramsey (K1,2, P4)-minimal graphs. Far East J. Math. Sci. 40 (1) (2010), 23–26.

Zhang, Y., Broersma, H., and Chen, Y. A remark on star-C4 and wheel-C4 Ramsey numbers. Electron. J. Graph Theory Appl. 2 (2) (2014), 110–114.


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