## 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