Isolation of connected graphs

Abstract

For a connected $n$-vertex graph $G$ and a set $\mathcal{F}$ of graphs, let $\iota (G,\mathcal{F})$ denote the size of a smallest set $D$ of vertices of $G$ such that the graph obtained from $G$ by deleting the closed neighbourhood of $D$ contains no graph in $\mathcal{F}$. Let ${\mathcal{E}}_k$ denote the set of connected graphs that have at least $k$ edges. By a result of Caro and Hansberg, $\iota (G,{\mathcal{E}}_1)\le n/3$ if $n\ne 2$ and $G$ is not a $5$-cycle. The author recently showed that if $G$ is not a triangle and $\mathcal{C}$ is the set of cycles, then $\iota (G,\mathcal{C})\le n/4$. We improve this result by showing that $\iota (G,{\mathcal{E}}_3)\le n/4$ if $G$ is neither a triangle nor a $7$-cycle. Let $r$ be the number of vertices of $G$ that have only one neighbour. We determine a set $\mathcal{S}$ of six graphs such that $\iota (G,{\mathcal{E}}_2)\le (4n-r)/14$ if $G$ is not a copy of a member of $\mathcal{S}$. The bounds are sharp.

19 pages