2024/08/26 by Borg, Peter, Lemańska, Magdalena, Mora, Mercè +1
#05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2408.14653
The isolation number of a graph G (also called the vertex-edge domination number of G), denoted by ι(G), is the size of a smallest subset D of the vertex set V(G) of G such that G-N[D] (the graph obtained by deleting the closed neighbourhood N[D] of D from G) has no edges. For k ≥ 1, the k-isolation number of G is the size of a smallest subset D of V(G) such that the maximum degree of G-N[D] is at most k-1. Thus, ι1(G) = ι(G). Let n and ℓ be the number of vertices and the number of leaves of G, respectively. We show that if n ≥ 3 and G is connected, then ιk(G) ≤ (n - ℓ)/(2). We also show that if G is a tree T, then ι(T) ≤ (n + ℓ)/(4) and ιk(T) ≤ (n + ℓ)/(2k+1) for k ≥ 2. These bounds together improve the inequality ιk(T) ≤ (n)/(k+2) of Caro and Hansberg except that their inequality is better if k ≥ 2 and (k-1)/(k+2)n < ℓ < (k)/(k+2)n. Each of the new bounds is attainable if it is an integer. For each of them, we characterize all the graphs that attain it.