On the isolation number of graphs with minimum degree four

2025/08/29 by Goddard, Wayne, Henning, Michael A.
#05c69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2508.21551

Abstract

An isolating set in a graph G is a set S of vertices such that removing S and its neighborhood leaves no edge. The isolation number ι(G) of G (also known as the vertex-edge domination number) is the minimum size among all isolating sets of G. We provide a technique for proving upper bounds on this parameter for graphs with a given minimum degree. For example, we show that if G has order~n and minimum degree at least~4, then ι(G) ≤ 13n/41, and if G is also triangle-free, then ι(G) ≤ 3n/10.

Citations

• Disjoint Isolating Sets and Graphs with Maximum Isolation Number
• Domination number of graphs with minimum degree five
• Partial domination - the isolation number of a graph
• Improved upper bounds on the domination number of graphs with minimum degree at least five

Cited by

• Bounds on the game isolation number and exact values for paths and cycles

Related

• Disjoint Isolating Sets and Graphs with Maximum Isolation Number
• Upper bounds on the k-isolation number
• Bounds on Independent Isolation in Graphs
• On the C₄-isolation number of a graph
• Partial domination of middle graphs