cp's OEIS Frontend

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

%I A284704 #20 Feb 16 2025 08:33:43
%S A284704 1,3,11,183,45707,2919292687
%N A284704 Number of dominating sets in the n-hypercube graph.
%H A284704 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DominatingSet.html">Dominating Set</a>
%H A284704 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>
%p A284704 f:= proc(n) local G, Cons, CC,B,i;
%p A284704     G:= [$0..2^n-1];
%p A284704     Cons:= map(t -> {t, seq(Bits:-Xor(t,2^j),j=0..n-1)}, G);
%p A284704     for i from 0 to 2^n-1 do CC[i]:= select(c -> max(c)=i, Cons) od:
%p A284704     B:= {{}};
%p A284704     for i from 0 to 2^n-1 do
%p A284704       B:= select(c -> andmap(s -> s intersect c <> {}, CC[i]),
%p A284704         map(t -> (t, t union {i}), B));
%p A284704     od;
%p A284704     nops(B);
%p A284704 end proc:
%p A284704 map(f, [$0..4]); # _Robert Israel_, Apr 07 2017
%t A284704 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 A284704 Cf. A290406 (minimal dominating sets), A295372 (total dominating sets).
%K A284704 nonn,more
%O A284704 0,2
%A A284704 _Eric W. Weisstein_, Apr 01 2017
%E A284704 a(5) from _Andrew Howroyd_, Apr 16 2018