New Bounds for Three Outer-Independent Domination-Related Parameters in Cactus Graphs

Abstract

Let G be a nontrivial connected graph. For a set D⊆V(G), we define D¯=V(G)∖D. The set D is a total outer-independent dominating set of G if |N(v)∩D|≥1 for every vertex v∈V(G) and D¯ is an independent set of G. Moreover, D is a double outer-independent dominating set of G if |N[v]∩D|≥2 for every vertex v∈V(G) and D¯ is an independent set of G. In addition, D is a 2-outer-independent dominating set of G if |N(v)∩D|≥2 for every vertex v∈D¯ and D¯ is an independent set of G. The total, double or 2-outer-independent domination number of G, denoted by γtoi(G), γ×2oi(G) or γ2oi(G), is the minimum cardinality among all total, double or 2-outer-independent dominating sets of G, respectively. In this paper, we first show that for any cactus graph G of order n(G)≥4 with k(G) cycles, γ2oi(G)≤n(G)+l(G)2+k(G), γtoi(G)≤2n(G)−l(G)+s(G)3+k(G) and γ×2oi(G)≤2n(G)+l(G)+s(G)3+k(G), where l(G) and s(G) represent the number of leaves and the number of support vertices of G, respectively. These previous bounds extend three known results given for trees. In addition, we characterize the trees T with γ×2oi(T)=γtoi(T). Moreover, we show that γ2oi(T)≥n(T)+l(T)−s(T)+12 for any tree T with n(T)≥3. Finally, we give a constructive characterization of the trees T that satisfy the equality above.

Keywords

• total outer-independent domination
• double outer-independent domination
• 2-outer-independent domination
• cactus graphs
• trees