Isolation of non-triangle cycles in graphs

Abstract

Given a set $\mathcal{F}$ of graphs, we call a copy of a graph in $\mathcal{F}$ an $\mathcal{F}$-graph. The $\mathcal{F}$-isolation number of a graph $G$, denoted by $\iota (G,\mathcal{F})$, is the size of a smallest set $D$ of vertices of $G$ such that the closed neighbourhood $N[D]$ of $D$ intersects the vertex sets of the $\mathcal{F}$-graphs contained by $G$ (equivalently, $G-N[D]$ contains no $\mathcal{F}$-graph). Let $\mathcal{C}$ be the set of cycles, and let ${\mathcal{C}}^{\prime }$ be the set of non-triangle cycles (that is, cycles of length at least $4$). Let $G$ be a connected graph having exactly $n$ vertices and $m$ edges. The first author proved that $\iota (G,\mathcal{C})\le n/4$ if $G$ is not a triangle. Bartolo and the authors determined a set ${\mathcal{E}}_4$ of nine graphs such that $\iota (G,\{C_4\})\le n/5$ if $G$ is not an ${\mathcal{E}}_4$-graph. Chen and Cui recently strengthened this result by proving that $\iota (G,{\mathcal{C}}^{\prime })\le n/5$ if $G$ is not an ${\mathcal{E}}_4$-graph. This had been proved by Zhang and Wu for the case where $G$ contains no triangle. Various authors proved that $\iota (G,\mathcal{C})\le (m+1)/5$ if $G$ is not a triangle. We prove that $\iota (G,{\mathcal{C}}^{\prime })\le (m+1)/6$ if $G$ is not a $4$-cycle. Zhang and Wu established this for the case where $G$ contains no triangle. Our result yields the inequality $\iota (G,\{C_4\})\le (m+1)/6$ of Wei, Zhang and Zhao. These bounds are attained by infinitely many (non-isomorphic) graphs. The proof of our inequality hinges on also determining the graphs attaining the bound.

arXiv comment12 pages, 1 figure, minor corrections made