A realization algorithm for double domination in graphs
Abstract
In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double (resp., triple) dominating set of G if S dominates every vertex of G at least twice (resp., thrice). The minimum cardinality of a double dominating set of G is the double domination number γ×2(G). A function f(p) is defined, and it is known that γ×2(G) = min/(p), where the minimum is taken over the n-dimensional cube Cn = {p = (p1,...,pn) | pi ∈ ℝ,0 ≤ pi ≤ 1, i = 1,..., n}. We present an efficient algorithm with INPUT: p ∈ Cn and a graph G of order n with δ(G) ≥ 1 and OUTPUT: a double dominating set D of G with \D\ ≤ f(p). Upper bounds on the double domination number of a graph in terms of its minimum degree, order, and domination number (resp., total domination number) are established. Further we present two results relating the k-tuple domination number of a graph and its independence number. An analogous continuous optimization problem for the triple domination number as well as a corresponding realization algorithm are established in the case when G is restricted to the class of graphs with the property that every vertex is contained in a triangle.
