Restricted domination parameters in graphs |
| |
Authors: | Wayne Goddard Michael A Henning |
| |
Institution: | (1) Department of Computer Science, Clemson University, Clemson, SC 29634, USA;(2) School of Mathematical Sciences, University of KwaZulu-Natal, Pietermaritzburg, 3209, South Africa |
| |
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.
Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. |
| |
Keywords: | Domination number Double domination k-domination Restricted |
本文献已被 SpringerLink 等数据库收录! |
|