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

Abstract

Given two graphs G₁, G₂, the connected size Ramsey number r_c(G₁, G₂) 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₁ or a blue copy of G₂. Concentrating on r_c(nK₂, G₂) where nK₂ 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 r_c(nK₂, P₃) 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 r_c(nK₂, C₄)≤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: r_c(nK₂, C₃)=4n − 1 for all positive integers n.