A bound on the $k$-domination number of a graph

Title:

A bound on the $k$-domination number of a graph

Creator:

Volkmann, Lutz

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:c3ffb22c-df20-493e-95c3-cddf77aeac49
uuid:c3ffb22c-df20-493e-95c3-cddf77aeac49

Subject:

domination, $k$-domination number, and $P_4$-free graphs

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

Let $G$ be a graph with vertex set $V(G)$, and let $k\ge 1$ be an integer. A subset $D \subseteq V(G)$ is called a {\it $k$-dominating set} if every vertex $v\in V(G)-D$ has at least $k$ neighbors in $D$. The $k$-domination number $\gamma _k(G)$ of $G$ is the minimum cardinality of a $k$-dominating set in $G$. If $G$ is a graph with minimum degree $\delta (G)\ge k+1$, then we prove that $$\gamma _{k+1}(G)\le \frac {|V(G)|+\gamma _k(G)}2.$$ In addition, we present a characterization of a special class of graphs attaining equality in this inequality.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

77-83

Source:

Czechoslovak Mathematical Journal | 2010 Volume:60 | Number:1

Harvested from:

CDK

Metadata only:

false