Independent and Fair-Domination in Hypercube

For a positive integer m , an m -dominating set of a graph G is a subset D ⊆ V(G) such that every vertex not in D is adjacent to at least m vertices in D . An m -dominating set D in which every vertex not in D is adjacent to exactly m vertices in D is known as the perfect m -dominating set. The perfect m -dominating set is also known as m -fair dominating set. The cardinality of a minimum fair-dominating set is known as the fair-domination number. The problem of deciding whether a graph admits a perfect m -dominating set is NP-Complete. In this paper we study the perfect m -dominating set with a variant such as independence in which no two vertices are adjacent, i.e. an independent perfect m -dominating set. The cardinality of a minimum independent dominating set is known as the independent domination number. We show that the hypercube graph of dimension 2 k+1 − 2, k being a positive integer > 1, is a perfect 2-dominating graph, i.e. the graph admits a perfect 2-dominating set which is an independent set. We compute in polynomial time an independent perfect 2-dominating set in hypercube graph Q n of dimension n = 2 k+1 −2 and showed that the 2-fair domination number for hypercube graph of this dimension is to be fd 2 (Q n ) ≤ 2 n−k , whereas the fair domination number for hypercube Q n of dimension 2 k − 1 is to be fd(Q n ) = 2 n−k . We also establish that the independent domination numbers are α n < O(fd 2 (Q n )) and α n = fd(Q n ) for hypercubes Q n of dimensions n = 2 k+1 − 2 and n = 2 k − 1, respectively.