2025/10/09 by Peter Borg, Dayle Scicluna, Borg, Peter +1
Computer Science · Engineering · #Advanced Graph Theory Research #graph theory and CDMA systems #Formal Methods in Verification
paper · pdf · doi:10.48550/arxiv.2510.08361
Given a set F of graphs, we call a copy of a graph in F an F-graph. The F-isolation number of a graph G, denoted by ι(G, F), is the size of a smallest set D of vertices of G such that the closed neighbourhood of D intersects the vertex sets of the F-graphs contained by G (equivalently, G-N[D] contains no F-graph). Let C be the set of cycles, and let C' be the set of non-triangle cycles (that is, cycles of length at least 4). Let G be a connected graph having exactly n vertices and m edges. The first author proved that ι(G,C) ≤ n/4 if G is not a triangle. Bartolo and the authors proved that ι(G,\C4\) ≤ n/5 if G is not a copy of one of nine graphs. Various authors proved that ι(G,C) ≤ (m+1)/5 if G is not a triangle. We prove that ι(G,C') ≤ (m+1)/6 if G is not a 4-cycle. Zhang and Wu established this for the case where G is triangle-free. Our result yields the inequality ι(G,\C4\) ≤ (m+1)/6 of Wei, Zhang and Zhao. These bounds are attained by infinitely many (non-isomorphic) graphs. The proof of our inequality hinges on also determining the graphs attaining the bound.