On Dominating Sets and Independent Sets of Graphs

Abstract

For a graph G on vertex set V = {1, …, n} let k = (k₁, …, k_n) be an integral vector such that 1 [les ] k_i [les ] d_i for i ∈ V, where d_i is the degree of the vertex i in G. A k-dominating set is a set D_k ⊆ V such that every vertex i ∈ V[setmn ]D_k has at least k_i neighbours in D_k. The k-domination number γ_k(G) of G is the cardinality of a smallest k-dominating set of G.

For k₁ = · · · = k_n = 1, k-domination corresponds to the usual concept of domination. Our approach yields an improvement of an upper bound for the domination number found by N. Alon and J. H. Spencer.

If k_i = d_i for i = 1, …, n, then the notion of k-dominating set corresponds to the complement of an independent set. A function f_k(p) is defined, and it will be proved that γ_k(G) = min f_k(p), where the minimum is taken over the n-dimensional cube Cⁿ = {p = (p₁, …, p_n) [mid ] p_i ∈ ℝ, 0 [les ] p_i [les ] 1, i = 1, …, n}. An [Oscr ](Δ²2^Δn-algorithm is presented, where Δ is the maximum degree of G, with INPUT: p ∈ Cⁿ and OUTPUT: a k-dominating set D_k of G with [mid ]D_k[mid ][les ]f_k(p).