Recently, Caro, Patk\'os, and Tuza (2022) introduced the concept of connected Tur\'an number. We study a similar parameter in Ramsey theory. Given two graphs G₁ and G₂, the size Ramsey number r̂(G₁,G₂) 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 G₁ or a blue subgraph G₂ is present in G. If we further restrict the host graph G to be connected, we obtain the connected size Ramsey number, denoted as r̂c(G₁,G₂). Erd{o}s and Faudree (1984) proved that r(nK₂,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(nK₂,K1,m) for $n=2,3$. We establish a more general result: for all positive integers m and n with m≥ (n²+2pn+n-3)/2, we have rc(nK1,p,K1,m)=n(m+p)-1. As a corollary, rc(nK₂,K1,m)=nm+n-1 for m≥ (n²+3n-3)/2. We also propose a conjecture for the interested reader.
No takes yet. Share an insight, caveat, or question.
Guo et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: