Bipartite Dominating Sets in Hypercubes.
Mark Ramras · Ars Combinatoria · 2005
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 ∈ Y is adjacent to some x ∈ 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. Definition 1 Let G be a bipartite graph with bipartition (X,Y ). A subset S of X is called a one-sided dominating set if every vertex y ∈ Y is adjacent to some x ∈ S, i.e. if N(S) = Y . S is a minimal onesided dominating set if no proper subset of S is a one-sided dominating set. It is a minimum one-sided dominating set if no one-sided dominating set contained in X has smaller cardinality. In that case, S is called a bipartite dominating set. Bipartite dominating sets have been studied by Haynes, Hedetniemi, and Slater [4] and by Hedetniemi and Laskar [5], [6]. Remark 1 A subset S of X is a one-sided dominating set ⇔ the only maximal independent set containing S is X. Notation. For any graph G, γ(G) denotes the minimum size of a dominating set in G. We denote by Qn the n-dimensional hypercube. Its bipartition (X,Y ) is given by X = {x ∈ Qn | wt(x) is even}, Y = {y ∈ Qn | wt(y) is odd} where wt(z), the weight of z, is the number of 1’s in the n-tuple z. Alternatively, if we think of the vertices of Qn as the subsets of {1, 2, . . . , n}, X consists of the subsets of even cardinality, and Y consists of the subsets of odd cardinality. We will also at times consider Qn to be a group under component-wise addition of n-tuples (or, if the vertices are thought of as subsets of {1, 2, . . . , n}, then under the operation of symmetric difference). The next proposition basically restates the Hamming Bound (see [9], p. 413), for Qn for single-error-correcting codes. Department of Mathematics, Northeastern University, Boston, MA 02115 ([email protected]), Tel: 617-373-5651, Fax: 617-373-5658.