Connected size Ramsey numbers of matchings versus a small path or cycle - Wang, Sha; Song, Ruyu; Zhang, Yixin; Zhang, Yanbo (Electronic Journal of Graph Theory and Applications (EJGTA), 2025)
Given two graphs G1, G2, the connected size Ramsey number rc(G1, G2) 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 G1 or a blue copy of G2. Concentrating on rc(nK2, G2) where nK2 is a matching, we generalise and improve two previous results as follows. Vito, Nabila, Safitri, and Silaban (J. Phys. Conf. Ser., 2021) obtained the exact values of rc(nK2, P3) for n = 2, 3, 4. We determine its exact values for all positive integers n. Rahadjeng, Baskoro, and Assiyatun (Proc. Indian Acad. Sci.: Math. Sci., 2017) proved that rc(nK2, C4)≤5n − 1 for n ≥ 4. We improve the upper bound from 5n − 1 to ⌊(9n − 1)/2⌋. In addition, we show a result which has the same flavour and has exact values: rc(nK2, C3)=4n − 1 for all positive integers n.