Upper Bounds on the k-Isolation Number

Abstract

[Abstract]: 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, denoted by ιk(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 and not a star, 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+2n <ℓ< k k+2n. Each of the new bounds is attainable if it is an integer. For each of them, we characterize the graphs that attain it.