Bounds of the 2-domination number of graphs

Abstract

A vertex set S of a graph G is a 2-dominating set of G if |N(v) ∩ S| ≥ 2 for every vertex v ∈ V(G) - S, where N(v) is the neighborhood of v. The 2-domination number γ₂(G) is the minimum cardinality among the 2-dominating sets of G. In this paper we present different lower and upper bounds of the 2-domination number. If G is a graph of order n, minimum degree δ ≥ 2, and domination number γ, then we show that γ₂(G) ≤ (n+γ)/2. In addition, if G is a block graph, then we prove that γ₂(G) ≥ β(G), where β(G) is the independence number of G. Examples will show that these results are best possible in some sense. Some related results are also presented.