A bound on the <Emphasis Type="Italic">k</Emphasis>-domination number of a graph |
| |
Authors: | Lutz Volkmann |
| |
Institution: | 1.Lehrstuhl II für Mathematik,RWTH Aachen University,Aachen,Germany |
| |
Abstract: | Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ
k
(G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that
$
\gamma _{k + 1} (G) \leqslant \frac{{|V(G)| + \gamma _k (G)}}
{2}.
$
\gamma _{k + 1} (G) \leqslant \frac{{|V(G)| + \gamma _k (G)}}
{2}.
|
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|
|