Improved Upper Bound on Independent Domination Number for Hypercubes
share
We revisit the problem of determining the independent domination number in hypercubes for which the known upper bound is still not tight for general dimensions. We present here a constructive method to build an independent dominating set S_n for the n-dimensional hypercube Q_n, where n=2p+1, p being a positive integer ≥ 1, provided an independent dominating set S_p for the p-dimensional hypercube Q_p, is known. The procedure also computes the minimum independent dominating set for all n=2^k-1, k>1. Finally, we establish that the independent domination number α_n≤ 3 × 2^n-k-2 for 7× 2^k-2-1≤ n<2^k+1-1, k>1. This is an improved upper bound for this range as compared to earlier work.
READ FULL TEXT