






















The $3$-path isolation number of a connected $n$-vertex graph $G$, denoted by $ι(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 the vertex sets of the $3$-vertex paths of $G$, meaning that no two edges of $G-N[D]$ intersect. If $G$ is not a $3$-path or a $3$-cycle or a $6$-cycle, then $ι(G,P_3) \leq 2n/7$. This was proved by Zhang and Wu, and independently by Borg in a slightly extended form. The bound is attained by infinitely many connected graphs having induced $6$-cycles. Huang, Zhang and Jin showed that if $G$ has no $6$-cycles, or $G$ has no induced $5$-cycles and no induced $6$-cycles, then $ι(G,P_3) \leq 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. Thus, the problem essentially is whether induced $6$-cycles solely account for the difference between the two bounds. In this paper, we solve this problem for subcubic graphs, which need to be treated differently from other graphs. We show that if $G$ is subcubic and has no induced $6$-cycles, then $ι(G,P_3) \leq n/4$ unless $G$ is a copy of one of $12$ particular graphs whose orders are $3$, $7$, $11$ and $15$. The bound is sharp.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。