Computing Independent Dominating Sets in Hypercube Graphs

Abstract An independent dominating set of a graph is a subset of vertices such that every vertex of the graph is either in he set or adjacent to a vertex in it, and no two vertices of the set are adjacent in the graph. An independent dominating set with the smallest cardinality is called the minimum independent dominating set. The independent domination number is the cardinality of the minimum independent dominating set. Finding a minimum independent dominating set in a graph is an NP-hard problem. This work computes in constant time the minimum independent dominating set in hypercube graph of dimension 2k , k being a positive integer ≥ 1. Furthermore, the independent dominating sets in the n-dimensional hypercube graphs, where 2k < n < 2k+1 −1, k being a positive integer ≥ 1, are computed in linear time. The cardinality of the computed independent dominating set in hypercube graphs of dimensions 2k < n < 2k+1 − 1 satisfies the upper bound of the independent domination number in hypercubes of these dimensions.