login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A284707 Number of maximal independent vertex sets in the n-hypercube graph Q_n. 3
1, 2, 2, 6, 42, 1670, 1281402 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
LINKS
Dwight Duffus, Peter Frankl, and Vojtěch Rödl, Maximal independent sets in bipartite graphs obtained from Boolean lattices, European Journal of Combinatorics 32.1 (2011): 1-9.
Dwight Duffus, Peter Frankl, and Vojtěch Rödl, Maximal independent sets in the covering graph of the cube, Discrete Applied Mathematics 161.9 (2013): 1203-1208.
Dmitry I. Ignatov, On the Maximal Independence Polynomial of the Covering Graph of the Hypercube up to n = 6, Int'l Conf. Formal Concept Analysis, 2023.
Liviu Ilinca and Jeff Kahn, Counting maximal antichains and independent sets, arXiv:1202.4427 [math.CO], Feb 2012; Order 30.2 (2013): 427-435.
Jeff Kahn and Jinyoung Park, The number of maximal independent sets in the Hamming cube, arXiv:1909.04283 [math.CO], 2019.
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
FORMULA
a(n) ~ 2*n*2^(N/4) where N = 2^n [Kahn and Park]. - N. J. A. Sloane, Sep 11 2019
MATHEMATICA
Table[Length @ FindIndependentVertexSet[HypercubeGraph[n], Infinity, All], {n, 0, 6}] (* Eric W. Weisstein, Jan 01 2024 *)
PROG
(Python)
from networkx import empty_graph, find_cliques
def A284707(n):
k = 1<<n
G = empty_graph(list(range(k)))
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))
return sum(1 for c in find_cliques(G)) # Chai Wah Wu, Jan 11 2024
CROSSREFS
Cf. A027624 (not necessarily maximal), A366425 (non-isomorphic).
Sequence in context: A290957 A032117 A137244 * A174589 A326942 A247943
KEYWORD
nonn,more
AUTHOR
Eric W. Weisstein, Apr 01 2017
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 06:05 EDT 2024. Contains 370952 sequences. (Running on oeis4.)