Connected size Ramsey numbers of matchings versus a small path or cycle

Sha Wang; Ruyu Song; Yixin Zhang; Yanbo Zhang

paper

Connected size Ramsey numbers of matchings versus a small path or cycle

arXiv:2205.03965

Abstract

Given two graphs $G_{1}, G_{2}$ , the connected size Ramsey number $r^_{c} (G_{1}, G_{2})$ is defined to be the minimum number of edges of a connected graph $G$ , such that for any red-blue edge colouring of $G$ , there is either a red copy of $G_{1}$ or a blue copy of $G_{2}$ . Concentrating on $r^_{c} (n K_{2}, G_{2})$ where $n K_{2}$ is a matching, we generalise and improve two previous results as follows. Vito, Nabila, Safitri, and Silaban obtained the exact values of $r^_{c} (n K_{2}, P_{3})$ for $n = 2, 3, 4$ . We determine its exact values for all positive integers $n$ . Rahadjeng, Baskoro, and Assiyatun proved that $r^_{c} (n K_{2}, C_{4}) \leq 5 n - 1$ for $n \geq 4$ . We improve the upper bound from $5 n - 1$ to $⌊(9 n - 1) /2 ⌋$ . In addition, we show a result which has the same flavour and has exact values: $r^_{c} (n K_{2}, C_{3}) = 4 n - 1$ for all positive integers $n$ .

9 pages