A360685 - OEIS

%I #14 Feb 16 2025 08:34:04

%S 1,2,4,4,40,120,240,240,11612160

%N Number of maximum independent vertex sets in the n-halved cube graph Q_n/2.

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

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

%t Table[With[{g = GraphPower[HypercubeGraph[n - 1], 2]}, Length[FindIndependentVertexSet[g, Length /@ FindIndependentVertexSet[g], All]]], {n, 8}]

%o (Python)

%o from collections import Counter

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

%o def A360685(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 (c:=Counter(len(c) for c in find_cliques(complement(power(G,2)))))[max(c)] # _Chai Wah Wu_, Jan 12 2024

%Y Cf. A290606.

%K nonn,more,hard

%O 1,2

%A _Eric W. Weisstein_, Feb 16 2023