2023/10/26 by Xiaohua Wei, Gang Zhang, Wei, Xiaohua +3 · 1 citation
Computer Science · Mathematics · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2310.17337
openalex publication_date 2023/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let Ck be the cycle of length k. For any graph G, a subset D ⊆ V(G) is a Ck-isolating set of G if the graph obtained from G by deleting the closed neighbourhood of D contains no Ck as a subgraph. The Ck-isolation number of G, denoted by ι(G,Ck), is the cardinality of a smallest Ck-isolating set of G. Borg (2020) and Borg et al. (2022) proved that if G \ncong C3 is a connected graph of order n and size m, then ι(G,C3) ≤ (n)/(4) and ι(G,C3) ≤ (m+1)/(5). Very recently, Bartolo, Borg and Scicluna showed that if G is a connected graph of order n that is not one of the determined nine graphs, then ι(G,C4) ≤ (n)/(5). In this paper, we prove that if G \ncong C4 is a connected graph of size m, then ι(G,C4) ≤ (m+1)/(6), and we characterize the graphs that attain the bound. Moreover, we conjecture that if G \ncong Ck is a connected graph of size m, then ι(G,Ck) ≤ (m+1)/(k+2).