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.