Abstract
In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ eqV(G) is an m-tuple dominating set if S dominates every vertex of G at least m times, and an m-dominating set if S dominates every vertex of G-S at least m times. The minimum cardinality of a dominating set is γ, of an m-dominating set is γ m , and of an m-tuple dominating set is mtupledom. For a property π of subsets of V(G), with associated parameter f_π, the k-restricted π-number r k (G,f_π) is the smallest integer r such that given any subset K of (at most) k vertices of G, there exists a π set containing K of (at most) cardinality r. We show that for 1< k < n where n is the order of G: (a) if G has minimum degree m, then r k (G,γ m ) < (mn+k)/(m+1); (b) if G has minimum degree 3, then r k (G,γ) < (3n+5k)/8; and (c) if G is connected with minimum degree at least 2, then r k (G,ddom) < 3n/4 + 2k/7. These bounds are sharp.
Original language | English |
---|---|
Pages (from-to) | 353-363 |
Number of pages | 11 |
Journal | Journal of Combinatorial Optimization |
Volume | 13 |
Issue number | 4 |
DOIs | |
Publication status | Published - May 2007 |
Externally published | Yes |
Keywords
- Domination number
- Double domination
- K-domination
- Restricted
ASJC Scopus subject areas
- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics