On double domination in graphs

Harant, Jochen GND; Henning, Mike GND

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) = minf(p), where the minimum is taken over the n-dimensional cube Cn = {p = (p1,…,pn) | pi ∈ IR, 0 ≤ pi ≤ 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.


Citation style:
Harant, J., Henning, M., Workshop on Graph Theory Colourings, I., Domination (CID), (Karpacz), ., 2005. On double domination in graphs. Discussiones mathematicae: Graph theory, Discussiones mathematicae: Graph theory 25, 2005, 29–34. https://doi.org/10.7151/dmgt.1256
Could not load citation form. Default citation form is displayed.


Use and reproduction: