A284704 Number of dominating sets in the n-hypercube graph.
1, 3, 11, 183, 45707, 2919292687
Offset: 0
Links
- Eric Weisstein's World of Mathematics, Dominating Set
- Eric Weisstein's World of Mathematics, Hypercube Graph
Programs
-
Maple
f:= proc(n) local G, Cons, CC,B,i; G:= [$0..2^n-1]; Cons:= map(t -> {t, seq(Bits:-Xor(t,2^j),j=0..n-1)}, G); for i from 0 to 2^n-1 do CC[i]:= select(c -> max(c)=i, Cons) od: B:= {{}}; for i from 0 to 2^n-1 do B:= select(c -> andmap(s -> s intersect c <> {}, CC[i]), map(t -> (t, t union {i}), B)); od; nops(B); end proc: map(f, [$0..4]); # Robert Israel, Apr 07 2017 -
Mathematica
Table[Count[Subsets[Range[2^n]], ?(CountDistinct[Flatten[# /. Table[k -> Prepend[AdjacencyList[HypercubeGraph[n], k], k], {k, 2^n}]]] == 2^n &)], {n, 0, 3}] (* _Eric W. Weisstein, May 19 2017 *)
Extensions
a(5) from Andrew Howroyd, Apr 16 2018