Mathematical analysis demonstrates extremal structures achieving subgraph isolation bounds, resolving an open conjecture in graph domination theory.
A copy of a graph F is called an F-copy. For any graph G, the F-isolation number of G, denoted by $ι(G,F)$, is the size of a smallest subset D of the vertex set of G such that the closed neighbourhood $N[D]$ of D in G intersects the vertex sets of the F-copies contained by G (equivalently, $G-N[D]$ contains no F-copy). Thus, ι(G,K₁) is the domination number $γ(G)$ of G, and ι(G,K₂) is the vertex-edge domination number of G. Settling a conjecture of Zhang and Wu, the first author proved that if F is a k-edge graph, $γ(F) = 1$ (that is, F has a vertex that is adjacent to all the other vertices of F), and G is a connected m-edge graph, then ι(G,F) ≤ m+1/k+2 unless G is an F-copy or F is a $3$-path and G is a $6$-cycle. We prove another conjecture of Zhang and Wu by determining the graphs that attain the bound.
No takes yet. Share an insight, caveat, or question.
Borg et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: