Proof of a conjecture on isolation of graphs with a universal vertex

Abstract

A copy of a graph $F$ is called an $F$-copy. For any graph $G$, the $F$-isolation number of $G$, denoted by $\iota (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, $\iota (G,K_1)$ is the domination number $\gamma (G)$ of $G$, and $\iota (G,K_2)$ 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, $\gamma (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 $\iota (G,F)\le \frac{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.

18 pages