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

2023/08/01 by Huang, Yirui, Zhang, Gang, Jin, Xian'an · 1 citation
#05C69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2308.00581

Abstract

Let G be a graph. A subset D ⊆ V(G) is called a 1-isolating set of G if Δ(G-N[D]) ≤ 1, that is, G-N[D] consists of isolated edges and isolated vertices only. The 1-isolation number of G, denoted by ι₁(G), is the cardinality of a smallest 1-isolating set of G. In this paper, we prove that if G ∉ \P₃,C₃,C₇,C₁₁\ is a connected graph of order n without 6-cycles, or without induced 5- and 6-cycles, then ι₁(G) ≤ (n)/(4). Both bounds are sharp.

Cited by

• Solution to a problem on isolation of 3-vertex paths

Related

• On the C₄-isolation number of a graph
• Isolation of non-triangle cycles in graphs
• Isolation of connected graphs
• Disjoint Isolating Sets and Graphs with Maximum Isolation Number
• Isolation of cycles