Bipartite Dominating Sets in Hypercubes

Abstract

If \(G\) is a bipartite graph with bipartition \((X,Y)\), a subset \(S\) of \(X\) is called a one-sided dominating set if every vertex \(y \in Y\) is adjacent to some \(x \in S\). If \(S\) is minimal as a one-sided dominating set (i.e., if it has no proper subset which is also a one-sided dominating set), it is called a bipartite dominating set (see \([4], [5]\), and \([6]\)). We study bipartite dominating sets in hypercubes.