proposed

approved

editing

proposed

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

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

proposed

editing

editing

proposed

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

All maximal independent vertex sets in the n-hypercube graph Q_n are given in A284707. Its independent vertex sets A027624.

Cf. A027624, A284707.

proposed

editing

editing

proposed

a(0) = 1 since {0} is the only maximal independent vertex set of Q_0, which is the graph consisting of a single vertex labeled 0.

a(1) = 2 since Q_1 = 0---1 has maximal independent vertex sets {0} and {1}, which are inequivalent.

a(0) = 1 since {0} is the only maximal independent vertex set of Q_0, which is the graph consisting of a single vertex labeled 0.

a(1) = 2 since Q_1 = 0---1 has maximal independent vertex sets {0} and {1}, which are inequivalent.

All maximal independent vertex sets in the n-hypercube graph Q_n are given in A284707. Its independent vertex sets A027624.

allocated for Dmitry I. Ignatov

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

1, 2, 2, 4, 10, 62, 3385

0,2

a(n) is the number of orbits for the corresponding families of maximal independent vertex sets in the n-hypercube graph Q_n (see also A284707) under the action of the symmetry group S_n.

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.

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.

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.

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.

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.

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

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

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

All maximal independent vertex sets in the n-hypercube graph Q_n are given in A284707.

allocated

nonn,more,hard

Dmitry I. Ignatov, Oct 09 2023

approved

editing

allocated for Dmitry I. Ignatov

allocated

approved