On double domination in graphs

Jochen Harant, and Michael A. Henning. "On double domination in graphs." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 29-34. <http://eudml.org/doc/270158>.

@article{JochenHarant2005,
abstract = {In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number $γ_\{×2\}(G)$. A function f(p) is defined, and it is shown that $γ_\{×2\}(G) = min f(p)$, where the minimum is taken over the n-dimensional cube $Cⁿ = \{p = (p₁,...,pₙ) | p_i ∈ IR, 0 ≤ p_i ≤ 1,i = 1,...,n\}$. Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then $γ_\{×2\}(G) ≤ ((ln(1+d) + lnδ + 1)/δ)n$.},
author = {Jochen Harant, Michael A. Henning},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {average degree; bounds; double domination; probabilistic method; dominating number},
language = {eng},
number = {1-2},
pages = {29-34},
title = {On double domination in graphs},
url = {http://eudml.org/doc/270158},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Jochen Harant
AU - Michael A. Henning
TI - On double domination in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 29
EP - 34
AB - In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number $γ_{×2}(G)$. A function f(p) is defined, and it is shown that $γ_{×2}(G) = min f(p)$, where the minimum is taken over the n-dimensional cube $Cⁿ = {p = (p₁,...,pₙ) | p_i ∈ IR, 0 ≤ p_i ≤ 1,i = 1,...,n}$. Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then $γ_{×2}(G) ≤ ((ln(1+d) + lnδ + 1)/δ)n$.
LA - eng
KW - average degree; bounds; double domination; probabilistic method; dominating number
UR - http://eudml.org/doc/270158
ER -