Characterization of \mathcal{R}(2K_2,F_n) with Minimum Order for Small n
Abstract
A Fan graph $F_n$ is defined as the graph $P_n+K_1$, where $P_n$ is the path on $n$ vertices. The notation $F \rightarrow (G, H)$ 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 $G$ or the subgraph of $F$ induced by all blue edges contains a graph $H.$ Let $\mathcal{R}(G, H)$ denote the set of all graphs $F$ satisfying $F \rightarrow (G, H)$ and for every $e \in E(F),$ $(F - e) \not\rightarrow (G, H).$ In this paper, we propose some properties for a graph $G$ of minimum order that belongs to $\mathcal{R}(2K_2,F_n),$ for $n \geq 3$. We have also found all members of $\mathcal{R}(2K_2,F_n)$ with a minimum order for $n \in [3,7]$.
Full text article
References
F. P. Ramsey, “On a problem of formal logic," in Proceedings of the London Mathematical Society, vol. 30, pp. 263-286, 1930. https://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseyorig.pdf.
S. A. Burr, P. Erdos, and L. Lov asz, “On graphs of ramsey type," Ars Combinatoria, vol. 1, pp. 167-190, 1976. https://api.semanticscholar.org/CorpusID:17474857.
R. Diestel, Graph Theory (5th. ed.). Springer Publishing Company, Incorporated, 2017. https://doi.org/10.1007/978-3-662-53622-3.
E. T. Baskoro, S. M. Nababan, and M. Miller, “On ramsey numbers for trees versus wheels of five or six vertices," Communications in Algebra, vol. 18, no. 4, pp. 717-721, 2002. https://doi.org/10.1007/s003730200056.
S. A. Burr, “Generalized ramsey theory for graphsa survey," Graphs and Combinatorics. Springer, Berlin, vol. 406, pp. 52-75, 1973. https://doi.org/10.1007/BFb0066435.
C. J. Jayawardene and C. C. Rousseau, “The ramsey number for a cycle of length five vs. a complete graph of order six," J. Graph Theory, vol. 35, pp. 99-108, 2000. https://doi.org/10.1002/1097-0118(200010)35:2<99::AID-JGT4>3.0.CO;2-6.
Surahmat, E. T. Baskoro, and H. J. Broersma, “The ramsey numbers of large cycles versus small wheels," INTEGERS Electron. J. Combin. Number Theory, vol. 4, no. 10, pp. 1-9,2004. https://www.kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/e10/e10.pdf.
T. Luczak, On ramsey minimal graphs," The Electronic Journal of Combinatorics, vol. 1, p. #R4, 1994. https://doi.org/10.37236/1184.
S. A. Burr, P. Erds, R. J. Faudree, and R. H. Schelp, “A class of ramsey-finite graphs," in Proceeding of the Ninth Southeastern Conference on Combinatorics, Graph Theory and Computing, pp. 171-180, 1978. https://static.renyi.hu/~p_erdos/1978-02.pdf.
E. T. Baskoro, T. Vetrk, and L. Yulianti, “A note on ramsey (K1;2; C4)-minimal graphs of diameter 2," in Proceedings of the International Conference 70 Years of FCE STUs, Bratislava, Slovakia, 2008.
E. T. Baskoro, L. Yulianti, and A. H., “Ramsey ( K1;2; C4)-minimal graphs," J. Combin. Math. Combin. Comput., vol. 65, pp. 79-90, 2008.
T. Vetrk, L. Yulianti, and B. E. T., “On ramsey ( K1;2; C4)-minimal graphs," Discuss. Math. Graph Theory, vol. 30, p. 637649, 2010. https://doi.org/10.7151/dmgt.1519.
L. Yulianti, H. Assiyatun, S. Uttunggadewa, and B. E. T., “On ramsey ( K1;2; P4)-minimal graphs," Far East J. Math. Sci., vol. 40, no. 1, pp. 23-26, 2010.
M. Borowiecki, I. Schiermeyer, and E. Sidorowicz, “Ramsey ( K1;2; K3)-minimal graphs,"Electron. J. Combin., vol. 12, no. R20, pp. 1-15, 2005. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r20/pdf.
M. Borowiecka-Olszewska and M. Haluszckak, “On ramsey ( K1;m; G)-minimal graphs," Discrete Math, vol. 313, no. 19, p. 18431855, 2012. https://doi.org/10.1016/j.disc.2012.06.020.
I. Mengersen and J. Oeckermann, “"matching-star ramsey sets," Discrete Appl. Math., vol. 95, pp. 417-424, 1999. https://doi.org/10.1016/S0166-218X(99)00089-X.
H. Muhshi and E. T. Baskoro, “On ramsey (3 K2; P3)-minimal graphs," in AIP Conf. Proc., vol. 1450, pp. 110-117, 2012. https://doi.org/10.1063/1.4940826.
E. T. Baskoro and L. Yulianti, “On ramsey minimal graphs for 2 K2 versus Pn," Adv. Appl. Discrete Math., vol. 8, no. 2, pp. 83-90, 2011.
D. Tatanto and B. E. T., “On ramsey (2 K2; 2Pn)-minimal graphs," in AIP Conference Proceedings, vol. 1450, pp. 90-95, 2012. https://doi.org/10.1063/1.4724122.
D. R. Silaban, A. I. Taufiq, and K. Wijaya, “On ramsey (mK2; P4)-minimal graphs," SIAM Journal on Discrete Mathematics, vol. 2, p. 467488, 2008. https://doi.org/10.2991/acsr.k.220202.003.
K. Wijaya, E. T. Baskoro, H. Assiyatun, and D. Suprijanto, “The complete list of ramsey (2K2; K4)-minimal graphs," Electron. J. Graph Theory Appl., vol. 3, no. 2, pp. 216-227, 2015. http://dx.doi.org/10.5614/ejgta.2015.3.2.9.
K. Wijaya, E. T. Baskoro, H. Assiyatun, and D. Suprijanto, “On unicyclic ramsey (mK2; P3)minimal graphs," Proc. Graph Theory, vol. 74, pp. 10-14, 2015. https://doi.org/10.1016/j.procs.2015.12.067.
E. T. Baskoro and W. K., “On ramsey (2 K2; K4)-minimal graphs," Mathematics in the 21st Century, Springer Proc. Math. Stat., vol. 98, pp. 11-17, 2015. https://doi.org/10.1007/978-3-0348-0859-0_2.
K. Wijaya, E. T. Baskoro, H. Assiyatun, and D. Suprijanto, “On ramsey ( mK2; H)minimal graphs," Graphs Comb., vol. 23, pp. 233-243, 2017. https://doi.org/10.1007/s00373-016-1748-1.
M. R. Fajri, A. H., and E. T. Baskoro, “On ramsey (2K2; Wn)-minimal graphs of smallest order," Electronic Journal of Graph Theory and Applications, 2024. (On Review).
M. R. Fajri, A. H., and E. T. Baskoro, “The characterization of ramsey (2 K2; F rn)-minimal graphs of smallest order," in AIP Conf. Proc., 2025. (Accepted).
Authors
Copyright (c) 2025 Journal of the Indonesian Mathematical Society
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Article Details
