## 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 C^{n} = {p = (p_{1},...,p_{n}) | pi ∈ ℝ,0 ≤ p_{i} ≤ 1, i = 1,..., n}. We present an efficient algorithm with INPUT: p ∈ C^{n} 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.

Original language | English |
---|---|

Pages (from-to) | 11-24 |

Number of pages | 14 |

Journal | Utilitas Mathematica |

Volume | 76 |

Publication status | Published - Jul 2008 |

Externally published | Yes |

## Keywords

- Bounds
- Double domination
- Probabilistic method
- Realization algorithm

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty
- Applied Mathematics