Balanced independent sets in hypercubes
Balanced independent sets in hypercubes
复制标题
超立方体中的平衡独立集
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Mark Ramras
中科院分区：
文献类型：
--
作者：
Mark Ramras
n维超立方体Qn有许多极大独立的顶点集。我们研究了那些平衡的最大独立集的基数，即刚好一半的顶点具有偶数权值，得到了最大值的上下界。对于n≤7，我们得到确切的值。对于所有奇数n，我们推测确切的值是2n−1−(n−1 (n−1)/2)。我们还考虑了当n为奇数时Qn的两个中间层的平衡独立子集，并证明了该子图的一个简单构造的平衡最大独立集具有任何平衡独立集的最大基数。它的基数是2·（n−1 (n−3)/2）。最后，从二元线性码中得到Qn中平衡极大独立集的一种方法，并利用Hamming码找到小基数的平衡极大独立集。
The n-dimensional hypercube Qn has many maximal independent sets of vertices. We study the cardinality of those maximal independent sets which are balanced , i.e. exactly half of whose vertices have even weight, obtaining both upper and lower bounds for the maximum value. For n ≤ 7 we obtain the exact value. For all odd n, we conjecture that the exact value is 2n−1 − ( n−1 (n−1)/2 ) . We also consider balanced independent subsets of the two middle levels of Qn when n is odd and prove that a simply constructed balanced maximal independent set for that subgraph has the maximum cardinality of any balanced independent set. Its cardinality is 2 · ( n−1 (n−3)/2 ) . Finally, one way in which balanced maximal independent sets in Qn arise is from binary linear codes, and we use Hamming codes to find balanced maximal independent sets of small cardinality.