A284704 - OEIS

%I #19 Apr 16 2018 23:53:59

%S 1,3,11,183,45707,2919292687

%N Number of dominating sets in the n-hypercube graph.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominatingSet.html">Dominating Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>

%p f:= proc(n) local G, Cons, CC,B,i;

%p     G:= [$0..2^n-1];

%p     Cons:= map(t -> {t, seq(Bits:-Xor(t,2^j),j=0..n-1)}, G);

%p     for i from 0 to 2^n-1 do CC[i]:= select(c -> max(c)=i, Cons) od:

%p     B:= {{}};

%p     for i from 0 to 2^n-1 do

%p       B:= select(c -> andmap(s -> s intersect c <> {}, CC[i]),

%p         map(t -> (t, t union {i}), B));

%p     od;

%p     nops(B);

%p end proc:

%p map(f, [$0..4]); # _Robert Israel_, Apr 07 2017

%t 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 *)

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

%K nonn,more

%O 0,2

%A _Eric W. Weisstein_, Apr 01 2017

%E a(5) from _Andrew Howroyd_, Apr 16 2018