Solution to a problem on isolation of $3$-vertex paths

Abstract

The $3$-path isolation number of a connected $n$-vertex graph $G$, denoted by ${\hat{I}}^1(G,P_3)$, 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 each $3$-vertex path of $G$, meaning that no two edges of $G-N[D]$ intersect. Zhang and Wu proved that ${\hat{I}}^1(G,P_3)\le 2n/7$ unless $G$ is a $3$-path or a $3$-cycle or a $6$-cycle. The bound is attained by infinitely many graphs having induced $6$-cycles. Huang, Zhang and Jin proved that if $G$ has no $6$-cycles, or $G$ has no induced $5$-cycles and no induced $6$-cycles, then ${\hat{I}}^1(G,P_3)\le n/4$ unless $G$ is a $3$-path or a $3$-cycle or a $7$-cycle or an $11$-cycle. They asked if the bound still holds asymptotically for connected graphs having no induced $6$-cycles. More precisely, taking $f(n)$ to be the maximum value of ${\hat{I}}^1(G,P_3)$ over all connected $n$-vertex graphs $G$ having no induced $6$-cycles, their question is whether ${\mathrm{limsup}}_{n\to \infty }\frac{f(n)}{n}=\frac{1}{4}$. We verify this by proving that $f(n)=\lfloor (n+1)/4\rfloor$. The proof hinges on further proving that if $G$ is such a graph and ${\hat{I}}^1(G,P_3)=(n+1)/4$, then ${\hat{I}}^1(G-v,P_3)<{\hat{I}}^1(G,P_3)$ for each vertex $v$ of $G$. This new idea promises to be of further use. We also prove that if the maximum degree of such a graph $G$ is at least $5$, then ${\hat{I}}^1(G,P_3)\le n/4$.

12 pages