Restricted domination parameters in graphs

Wayne Goddard, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

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 languageEnglish
Pages (from-to)353-363
Number of pages11
JournalJournal of Combinatorial Optimization
Volume13
Issue number4
DOIs
Publication statusPublished - May 2007
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Restricted domination parameters in graphs'. Together they form a unique fingerprint.

Cite this