On Dominating Sets and Independent Sets of Graphs

Source abstract

For a graph G on vertex set V = {1, …, n } let k = ( k 1 , …, 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 1 = · · · = 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 n = { p = ( p 1 , …, p n ) [mid ] p i ∈ ℝ, 0 [les ] p i [les ] 1, i = 1, …, n }. An [Oscr ](Δ 2 2 Δ n -algorithm is presented, where Δ is the maximum degree of G , with INPUT: p ∈ C n and OUTPUT: a k -dominating set D k of G with [mid ] D k [mid ][les ] f k ( p ).