A284704 Number of dominating sets in the n-hypercube graph.

1, 3, 11, 183, 45707, 2919292687

Offset: 0

Author

Eric W. Weisstein, Apr 01 2017

Keywords

• nonn
• more

Links

• Eric Weisstein's World of Mathematics, Dominating Set
• Eric Weisstein's World of Mathematics, Hypercube Graph

Crossrefs

Cf. A290406 (minimal dominating sets), A295372 (total dominating sets).

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