2024/04/04 by Fanghua Guo, Yanbo Zhang, Guo, Fanghua +3
Computer Science · #05C55 #05D10 #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Distributed systems and fault tolerance #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2404.03175
openalex publication_date 2024/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recently, Caro, Patkós, and Tuza (2022) introduced the concept of connected Turán number. We study a similar parameter in Ramsey theory. Given two graphs G1 and G2, the size Ramsey number r(G1,G2) refers to the smallest number of edges in a graph G such that for any red-blue edge-coloring of G, either a red subgraph G1 or a blue subgraph G2 is present in G. If we further restrict the host graph G to be connected, we obtain the connected size Ramsey number, denoted as rc(G1,G2). Erdős and Faudree (1984) proved that r(nK2,K1,m)=mn for all positive integers m,n. In this paper, we concentrate on the connected analog of this result. Rahadjeng, Baskoro, and Assiyatun (2016) provided the exact values of rc(nK2,K1,m) for n=2,3. We establish a more general result: for all positive integers m and n with m≥ (n2+2pn+n-3)/2, we have rc(nK1,p,K1,m)=n(m+p)-1. As a corollary, rc(nK2,K1,m)=nm+n-1 for m≥ (n2+3n-3)/2. We also propose a conjecture for the interested reader.