Isolation of cycles

Abstract

For any graph $G$, let ${\iota }_{\mathrm{c}}(G)$ 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 cycle. We prove that if $G$ is a connected $n$-vertex graph that is not a triangle, then ${\iota }_{\mathrm{c}}(G)\le n/4$. We also show that the bound is sharp. Consequently, we solve a problem of Caro and Hansberg.

7 pages