Connected Size Ramsey Numbers for Matchings versus Paths, Cycles, or Stars
Leonardo Boas Sando Saragih (a), Denny Riama Silaban (a*), and Peter John (a)

a) Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Indonesia, Depok, 16424, Indonesia
*denny[at]sci.ui.ac.id

Abstract

Let \(F\), \(G\), and \(H\) be simple and nontrivial graphs. The notation \(F\rightarrow(G, H)\) means that in any red-blue coloring of the edges of \(F\) there exists a red colored subgraph isomorphic to \(G\) or a blue colored subgraph isomorphic to \(H\). The connected size Ramsey number from a pair of graphs \(G\) and \(H\), denoted by \(\widehat{r}_{c}(G, H)\), is the smallest integer \(\widehat{r}_{c}\) such that there is a connected graph \(F\) with order \(\widehat{r}_{c}\) satisfying \(F\rightarrow(G, H)\). A matching graph \(nK_{2}\) is a disjoint union of \(n\) copy of \(K_{2}\), where \(n\geq2\). In this paper, we obtain the exact values of \(\widehat{r}_{c}(6K_{2}, P_{4})\), upper bound of \(\widehat{r}_{c}(3K_{2}, 2P_{m})\) for \(m\geq3\) and obtain the exact value of \(\widehat{r}_{c}(3K_{2}, 2P_{4})\). We also obtain the exact values of \(\widehat{r}_{c}(2K_{2}, C_{m})\) for \(m\in\left\{4, 5, 6\right\}\). Finally, we determine an upper bound of \(\widehat{r}_{c}(nK_{2}, tK_{1, m})\) for \(m\geq3\), \(n\geq2\), \(m>n\), \(t\geq1\) and obtain the exact values for \(t\in\left\{1, 3\right\}\).

Keywords: Connected size Ramsey number- cycles- matchings- paths- stars

Topic: Mathematics