Answers are grounded in this paper and cite their sources.
Determining the 3-path isolation number in graphs without induced cycles, suggesting a limit of n/4.
The $3$-path isolation number of a connected n-vertex graph G, denoted by ι(G,P₃), 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 ι(G,P₃) ≤ 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 ι(G, P₃) ≤ 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 ι(G,P₃) over all connected n-vertex graphs G having no induced $6$-cycles, their question is whether n →∞f(n)/n = 1/4. We verify this by proving that f(n) = (n+1)/4. The proof hinges on further proving that if G is such a graph and ι(G, P₃) = (n+1)/4, then ι(G-v, P₃) < ι(G, P₃) 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 ι(G,P₃) ≤ n/4.
No takes yet. Share an insight, caveat, or question.
Bartolo et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: