Relating the super domination and 2-domination numbers in cactus graphs

Abstract

A set D⊆V(G)D\subseteq V\left(G) is a super dominating set of a graph GG if for every vertex u∈V(G)\Du\in V\left(G)\setminus D, there exists a vertex v∈Dv\in D such that N(v)\D={u}N\left(v)\setminus D=\left\{u\right\}. The super domination number of GG, denoted by γsp(G){\gamma }_{sp}\left(G), is the minimum cardinality among all super dominating sets of GG. In this article, we show that if GG is a cactus graph with k(G)k\left(G) cycles, then γsp(G)≤γ2(G)+k(G){\gamma }_{sp}\left(G)\le {\gamma }_{2}\left(G)+k\left(G), where γ2(G){\gamma }_{2}\left(G) is the 2-domination number of GG. In addition, and as a consequence of the previous relationship, we show that if TT is a tree of order at least three, then γsp(T)≤α(T)+s(T)−1{\gamma }_{sp}\left(T)\le \alpha \left(T)+s\left(T)-1 and characterize the trees attaining this bound, where α(T)\alpha \left(T) and s(T)s\left(T) are the independence number and the number of support vertices of TT, respectively.

Keywords

• super domination number
• 2-domination number
• cactus graphs
• trees
• 05c69