New results on the 1-isolation number of graphs without short cycles

Abstract

Let $G$ be a graph. A subset $D\subseteq V(G)$ is called a 1-isolating set of $G$ if $\Delta (G-N[D])\le 1$, that is, $G-N[D]$ consists of isolated edges and isolated vertices only. The $1$-isolation number of $G$, denoted by ${\iota }_1(G)$, is the cardinality of a smallest $1$-isolating set of $G$. In this paper, we prove that if $G\notin \{P_3,C_3,C_7,C_{11}\}$ is a connected graph of order $n$ without $6$-cycles, or without induced 5- and 6-cycles, then ${\iota }_1(G)\le \frac{n}{4}$. Both bounds are sharp.

21 pages, 10 figures