login
Number of maximal independent vertex sets in the n-hypercube graph Q_n.
3

%I #37 Jan 11 2024 00:46:25

%S 1,2,2,6,42,1670,1281402

%N Number of maximal independent vertex sets in the n-hypercube graph Q_n.

%H Dwight Duffus, Peter Frankl, and Vojtěch Rödl, <a href="https://doi.org/10.1016/j.ejc.2010.08.004">Maximal independent sets in bipartite graphs obtained from Boolean lattices</a>, European Journal of Combinatorics 32.1 (2011): 1-9.

%H Dwight Duffus, Peter Frankl, and Vojtěch Rödl, <a href="https://doi.org/10.1016/j.dam.2010.09.003">Maximal independent sets in the covering graph of the cube</a>, Discrete Applied Mathematics 161.9 (2013): 1203-1208.

%H Dmitry I. Ignatov, <a href="https://doi.org/10.1007/978-3-031-35949-1_11">On the Maximal Independence Polynomial of the Covering Graph of the Hypercube up to n = 6</a>, Int'l Conf. Formal Concept Analysis, 2023.

%H Liviu Ilinca and Jeff Kahn, <a href="https://arxiv.org/abs/1202.4427">Counting maximal antichains and independent sets</a>, arXiv:1202.4427 [math.CO], Feb 2012; Order 30.2 (2013): 427-435.

%H Jeff Kahn and Jinyoung Park, <a href="https://arxiv.org/abs/1909.04283">The number of maximal independent sets in the Hamming cube</a>, arXiv:1909.04283 [math.CO], 2019.

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

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

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

%F a(n) ~ 2*n*2^(N/4) where N = 2^n [Kahn and Park]. - _N. J. A. Sloane_, Sep 11 2019

%t Table[Length @ FindIndependentVertexSet[HypercubeGraph[n], Infinity, All], {n, 0, 6}] (* _Eric W. Weisstein_, Jan 01 2024 *)

%o (Python)

%o from networkx import empty_graph, find_cliques

%o def A284707(n):

%o k = 1<<n

%o G = empty_graph(list(range(k)))

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

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

%Y Cf. A027624 (not necessarily maximal), A366425 (non-isomorphic).

%K nonn,more

%O 0,2

%A _Eric W. Weisstein_, Apr 01 2017