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

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

Offset

1,2

Links

Table of n, a(n) for n=1..9.

Eric Weisstein's World of Mathematics, Halved Cube Graph.

Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set.

Mathematica

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

Prog

(Python)
from collections import Counter
from networkx import empty_graph, find_cliques, complement, power
def A360685(n):
    k = 1<<n-1
    G = empty_graph(range(k))
    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))
    return (c:=Counter(len(c) for c in find_cliques(complement(power(G, 2)))))[max(c)] # Chai Wah Wu, Jan 12 2024

Crossrefs

Cf. A290606.

Sequence in context: A137787 A225171 A320600 * A290606 A155952 A277445

Adjacent sequences: A360682 A360683 A360684 * A360686 A360687 A360688

Keyword

nonn,more,hard

Author

Eric W. Weisstein, Feb 16 2023

Status

approved