A remark on the (2,2)-domination number

Torsten Korneffel, Dirk Meierling, and Lutz Volkmann. "A remark on the (2,2)-domination number." Discussiones Mathematicae Graph Theory 28.2 (2008): 361-366. <http://eudml.org/doc/270462>.

@article{TorstenKorneffel2008,
abstract = {A subset D of the vertex set of a graph G is a (k,p)-dominating set if every vertex v ∈ V(G)∖D is within distance k to at least p vertices in D. The parameter $γ_\{k,p\}(G)$ denotes the minimum cardinality of a (k,p)-dominating set of G. In 1994, Bean, Henning and Swart posed the conjecture that $γ_\{k,p\}(G) ≤ (p/(p+k))n(G)$ for any graph G with δₖ(G) ≥ k+p-1, where the latter means that every vertex is within distance k to at least k+p-1 vertices other than itself. In 2005, Fischermann and Volkmann confirmed this conjecture for all integers k and p for the case that p is a multiple of k. In this paper we show that $γ_\{2,2\}(G) ≤ (n(G)+1)/2$ for all connected graphs G and characterize all connected graphs with $γ_\{2,2\} = (n+1)/2$. This means that for k = p = 2 we characterize all connected graphs for which the conjecture is true without the precondition that δ₂ ≥ 3.},
author = {Torsten Korneffel, Dirk Meierling, Lutz Volkmann},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; distance domination number; p-domination number; -domination number},
language = {eng},
number = {2},
pages = {361-366},
title = {A remark on the (2,2)-domination number},
url = {http://eudml.org/doc/270462},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Torsten Korneffel
AU - Dirk Meierling
AU - Lutz Volkmann
TI - A remark on the (2,2)-domination number
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 2
SP - 361
EP - 366
AB - A subset D of the vertex set of a graph G is a (k,p)-dominating set if every vertex v ∈ V(G)∖D is within distance k to at least p vertices in D. The parameter $γ_{k,p}(G)$ denotes the minimum cardinality of a (k,p)-dominating set of G. In 1994, Bean, Henning and Swart posed the conjecture that $γ_{k,p}(G) ≤ (p/(p+k))n(G)$ for any graph G with δₖ(G) ≥ k+p-1, where the latter means that every vertex is within distance k to at least k+p-1 vertices other than itself. In 2005, Fischermann and Volkmann confirmed this conjecture for all integers k and p for the case that p is a multiple of k. In this paper we show that $γ_{2,2}(G) ≤ (n(G)+1)/2$ for all connected graphs G and characterize all connected graphs with $γ_{2,2} = (n+1)/2$. This means that for k = p = 2 we characterize all connected graphs for which the conjecture is true without the precondition that δ₂ ≥ 3.
LA - eng
KW - domination; distance domination number; p-domination number; -domination number
UR - http://eudml.org/doc/270462
ER -