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

This paper studies the \(1\)-isolation number of graphs under restrictions on short cycles. Recall that a subset \(D \subseteq V(G)\) is called a \(1\)-isolating set of a graph \(G\) if the graph \(G - N[D]\) consists only of isolated vertices and isolated edges. The minimum cardinality of such a set is the \(1\)-isolation number of \(G\), denoted by \(\iota_1(G)\). This notion is a natural extension of the classical isolation number and of domination theory.\N\NThe main results are Theorems~1.6 and~1.7. In Theorem~1.6, the authors prove that if \(G\) is a connected graph of order \(n\), not isomorphic to \(P_3\), \(C_3\), \(C_7\), or \(C_{11}\), and containing no \(6\)-cycles, then\N\[\N\iota_1(G) \le \left\lfloor \frac{n}{4} \right\rfloor .\N\]\NIn Theorem~1.7, the same upper bound is obtained under the weaker assumption that \(G\) contains no induced \(5\)- or \(6\)-cycles. In both cases, the bound \(\lfloor n/4 \rfloor\) is attained by infinitely many graphs.\N\NThese results extend earlier bounds on \(\iota_1(G)\) for trees, cycles, and graphs with large girth, and in particular strengthen previous results of \textit{G. Zhang} and \textit{B. Wu} [ibid. 304, 365--374 (2021; Zbl 1473.05235)] by replacing girth conditions with more refined forbidden subgraph assumptions. Explicit infinite families of extremal graphs are constructed to demonstrate that the bound \(n/4\) cannot be improved in general.\N\NThe proofs are carried out by induction on the order of the graph. A central role is played by vertices of maximum degree and by a detailed analysis of the components of the graph obtained after deleting closed neighborhoods \(N[v]\). The authors perform an extensive case analysis to control the interaction between forbidden cycles and the local structure of the graph, carefully distinguishing components isomorphic to small exceptional graphs from the remaining components. Several structural lemmas are repeatedly applied to reduce the problem to smaller graphs while preserving the absence of the specified short cycles.\N\NOverall, the paper contributes to the study of isolation and domination-type parameters in graphs with restricted cycle structure and provides sharp bounds for the \(1\)-isolation number under natural forbidden subgraph conditions.