login
Number of maximal independent vertex sets (and minimal vertex covers) in the n-halved cube graph.
3

%I #19 Jan 27 2024 11:41:30

%S 1,2,4,4,40,136,8080,17331120

%N Number of maximal independent vertex sets (and minimal vertex covers) in the n-halved cube graph.

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

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalVertexCover.html">Minimal Vertex Cover</a>.

%t Table[Length@FindIndependentVertexSet[GraphPower[HypercubeGraph[n - 1], 2], Infinity, All], {n, 7}]

%o (Python)

%o from networkx import empty_graph, find_cliques, complement, power

%o def A290606(n):

%o k = 1<<n-1

%o G = empty_graph(range(k))

%o G.add_edges_from((a,b) for a in range(k) for b in range(a) if (lambda m: not(m&-m)^m if m else False)(a^b))

%o return sum(1 for c in find_cliques(complement(power(G,2)))) # _Chai Wah Wu_, Jan 11 2024

%Y Cf. A288943.

%K nonn,more

%O 1,2

%A _Eric W. Weisstein_, Aug 07 2017