太原理工大学，数学学院，山西 晋中

收稿日期：2022年2月21日；录用日期：2022年3月15日；发布日期：2022年3月22日

摘要

编码理论中的一个基本问题是求 $A\left(n,d,w\right)$ 的值，即长度为n，重量为w，最小Hamming距离为d的二元码集的大小。它可看作是n维超立方体 $d-1$ 次幂图中所有重量为w的点导出子图 $Q_n^{\left(d-1,w\right)}$ 的最大独立集。本文运用构造图 $Q_n^{\left(d-1,w\right)}$ 的最大独立集的方法得到n、d和w为某些特殊值时， $A\left(n,d,w\right)=4$。

关键词

超立方体，最大独立集，常重码

A Class of Independent Sets of Subgraphs Derived from Constant Focus Sets in Hypercube Power Graphs

Juanjuan Shi, Weihua Yang^*

School of Mathematics, Taiyuan University of Technology, Jinzhong Shanxi

Received: Feb. 21^st, 2022; accepted: Mar. 15^th, 2022; published: Mar. 22^nd, 2022

ABSTRACT

A basic problem in coding theory is to find the value of $A\left(n,d,w\right)$, that is, the size of the maximum binary code with length n, constant weight w and minimum Hamming distance d. It can also be regarded as the maximum independent set of induced subgraph of points of weight w of the $d-1$ ^th-power of n-dimensional hypercube $Q_n^{\left(d-1,w\right)}$. We use the method of constructing the maximum independent set of $Q_n^{\left(d-1,w\right)}$ to obtain $A\left(n,d,w\right)=4$ for some special n, d and w.

Keywords:Hypercube, Maximum Independent Set, Constant Weight Code

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

1.1. 背景介绍

在编码理论中，常重码是一种有检错和纠错能力的重要编码，被广泛的应用于光导纤维中的码分多址系统、雷达和声纳的信号设计、高数据率数字通信等领域。由于其广泛的应用背景，常重码吸引了许多的学者参与研究。数学家们尝试用代数、图论以及组合等方法来研究满足一定条件的最大常重码的个数及其结构，并取得了很大的进展。但迄今为止，最大常重码的个数及其结构还未得到完整的结论。经研究发现编码理论和图论之间存在联系，可通过使用图论的方法研究常重码。

1.2. 相关工作

令 $Z=Z_2\times Z_2\times \cdots \times Z_2=Z_2^n$，则Z中的元素称为码字。码字x的重量由wt(x)表示，是其非零项的数量。码字的集合称为码集。w常重码是指其中所有的码字的重量都为w。令X是 $Z_2$ 上n维向量空间。X中的向量称为码字。两个代码词c和 $c^{\prime }$ 之间的Hamming距离 $d_H\left(c,c^{\prime }\right)$ 被定义为它们具有不同的坐标位置的数量。 $A\left(n,d,w\right)$ 是长度为n、重量为w和最小Hamming距离为d的最大二进制代码的大小。在经典编码理论中，寻找 $A\left(n,d,w\right)$ 的值是一个非常困难的问题，迄今没有完全解决，在 [1] 中有描述。

1950年，Hamming [2] 提出了球包界，特别地， $A\left(n,6,w\right)$ 的球包界为 $\frac{\left(\begin{array}{c}n\\ m\end{array}\right)}{w\left(n-w\right)+1}$。1962年，Johnson [3] 获得了 $A\left(n,d,w\right)$ 的上界，即 $A\left(n,d,w\right)\le \frac{dn}{dn-2w\left(n-w\right)}$。1977 年，MacWilliams和Sloane [4] 提出了第一个关于 $A\left(n,d,w\right)$ 与 $n\le 24$ 和 $d\le 10$ 界限的系统表。直到2000年，Vardy等人 [5] 改进了 $A\left(n,d,w\right)$ 的已知上界，即 $A\left(n,2\delta ,w\right)\le \frac{\left(\begin{array}{c}n\\ w-\delta +1\end{array}\right)}{\left(\begin{array}{c}w\\ w-\delta +1\end{array}\right)}$，他们还将表扩展到 $n\le 28$ 和 $d\le 14$。1989年，Cornelis等人 [6] 显著提高了 $A\left(n,4,w\right)$ 的界。在1990年，Brouwer等 [7] 通过大量针对某些参数的新显式代码构造，收集了 $n\le 28$ 和 $d\le 18$ 的 $A\left(n,d,w\right)$ 的著名下界。

总的来看，不少研究都致力利用半正定规划、Terwilliger代数等方法对 $A\left(n,d,w\right)$ 的上下界进行讨论，但大多都是对d取6，8，10，12时 $A\left(n,d,w\right)$ 的上下界有了一定的改进 [8] - [13]，对于确切的值，迄今为止还没有统一的方法去研究。本文提出从图论的角度去研究，将 $A\left(n,d,w\right)$ 看作是n维超立方体d-1次幂图中所有重量为w的点导出子图 $Q_n^{\left(d-1,w\right)}$ 的最大独立集，即 $A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)$。

1.3. 本文贡献

本文对最小Hamming距离为d、重量为w的最大n长二元常重码集的大小进行研究，利用

$A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)$，得到了如下结果：对于 $n,d,w\in {\text{Z}}^{+}$，d为偶数，如果 $\frac{2n+2}{5}\le d\le \frac{3n-2}{5}$，$\frac{3d-n}{2}\le w\le \frac{5d-n-1}{5}$ 或 $\frac{6n-5d+1}{5}\le w\le \frac{3n-3d}{2}$，则 $A\left(n,d,w\right)=4$ ；如果 $\frac{2d+1}{3}\le w\le \frac{3d}{4}$，$n-w+1\le d\le \frac{n+2w}{3}$，或 $\frac{11d-8}{12}\le w\le d-1$，$\frac{4n-4w}{3}\le d\le \frac{3n-3w-1}{2}$，则 $A\left(n,d,w\right)=4$ ；如果 $n=\frac{3d}{2}+1$，$d=\frac{4w-2}{3}$，则 $A\left(n,d,w\right)=4$。

2. 预备知识

本节给出本文需要的基本概念和符号。

令G是一个顶点集为 $V\left(G\right)$ 且边集为 $E\left(G\right)$ 的图。设 $S\subseteq V\left(G\right)$，如果在图G中S的顶点是两两独立的，则S称为图G的独立集，G的独立数 $\alpha \left(G\right)$ 是最大独立集的顶点数，如果图S的顶点在G中两两相邻，S称为图G的团，团数 $\omega \left(G\right)$ 等于最大团的顶点数，即 $\alpha \left(G\right)=\omega \left(\bar{G}\right)$。

定义2.1：图 $Q_n^d$ 表示n维超立方体 $Q_n$ 的d^th次幂图，其顶点集 $V\left(Q_n^d\right)=\left\{x|x\in Z_2^n\right\}$。也就是说对于任意的 $x,y\in V\left(Q_n^d\right)$，有边 $x~y$ 当且仅当 $d_H\left(x,y\right)\le d$。

定义2.2：图 $Q_n^{\left(d,w\right)}$ 表示图 $Q_n^d$ 的重量为w的点的导出子图，其顶点集 $V\left(Q_n^{\left(d,w\right)}\right)=\left\{x|x\in Z_2^n\right\}$。

定义2.3： $G=\left(V\left(G\right),E\left(G\right)\right)$ 为简单无向图，若对任意的 $x,y\in G$，存在 $\phi \in Aut\left(G\right)$ 满足 $\phi \left(x\right)=y$，

则图G为点传递图。

定义2.4 [14]： $Q_n^{\left(d,w\right)}$ 是点传递图。

定义2.5：给出两个n长二元码字 $x=\left(x_1,x_2,\cdots ,x_n\right),y=\left(y_1,y_2,\cdots ,y_n\right)$，定义 $x\cap y=\left\{i|x_i=y_i=1,1\le i\le n\right\}$。

定理2.6 [15]：设d，w，n是整数， $d\ne 0,w\le n$。然后，

(i) $A\left(n,d-1,w\right)=A\left(n,d,w\right)$，如果d是偶数，

(ii) $A\left(n,d,w\right)=A\left(n,d,n-w\right)$，

(iii) $A\left(n,d,w\right)=1$，如果 $d>2w$，

(iv) $A\left(n,d,w\right)=\frac{n}{w}$，如果 $d=2w$。

因为 $Q_n^{\left(d,w\right)}$ 是点可传递的，要研究它的独立数，我们只需要分析它的它包含顶点 $u^0=\left(u_1^0,u_2^0,\cdots ,u_n^0\right)$，$u_1^0=u_2^0=\cdots =u_w^0=1$，$u_{w+1}^0=u_{w+2}^0=\cdots =u_n^0=0$ 的最大独立集。接下来，令 $D_i^w\left(u^0\right)$ ( $0\le i\le 2w$ (或 $2\left(n-w\right)$ )，i是偶数)表示到 $u^0$ 的距离为i的顶点集，在下图(见图1)我们给出了图 $Q_n^{\left(d,w\right)}$ 相对于顶点 $u^0$ 的距离划分。在下文中，对于图中的任何 $u\in Q_n^{\left(d,w\right)}$，我们使用 $u_i$ 来表示其第i位的值。

图1. $Q_n^{\left(d,w\right)}$ 的距离划分

3. 主要结论及其证明

引理3.1：对于 $n,d,w\in {\text{Z}}^{+}$，d为偶数，设M是 $Q_n^{\left(d-1,w\right)}$ 的独立集，如果 $\frac{d}{2}\le w\le \frac{3d}{4}$，且 $n\ge 3d-2w$，则 $\left|M\cap Q_n^{\left(d-1,w\right)}\right|\ge 4$。设 $u_0,s,t,r\in M$，$c_1=\left|\left\{j|s_j=r_j=1,t_j=0,w+1\le j\le n\right\}\right|$，$c_2=\left|\left\{j|t_j=r_j=1,s_j=0,w+1\le j\le n\right\}\right|$，$c_3=\left|\left\{j|r_j=1,w+1\le j\le n\right\}\right|-c_1-c_2$，$c=\left|\left\{j|s_j=t_j=r_j=0,w+1\le j\le n\right\}\right|$。则有 $c_1,c_2\le w-\frac{d}{2}$，$c+c_3\le n-\frac{3d}{2}$，$c\le n+2w-3d$。

证明：令 $H_1=D_0^w\cap D_2^w\cap \cdots \cap D_{d-2}^w$，$H_2=D_d^w\cap D_{d+2}^w\cap \cdots \cap D_{2w}^w$，则 $V\left(Q_n^{\left(d-1,w\right)}\right)=H_1\cap H_2$。不妨设 $u^0\in M$，则对任意 $x\in H_1$ 且 $x\ne u^0$，有 $d_H\left(x,u^0\right)\le d-2<d$。因此， $M\cap H_1=u^0$。

因为 $w-\frac{d}{2}\ge 0$，$\frac{3d}{2}-2w\ge 0$，$n+2w-3d\ge 0$，所以至少存在三个点

$x=(\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}},\stackrel{\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}},\stackrel{n-w-\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}}),$

$y=(\stackrel{w-\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{d-w}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{d-w}{\stackrel{︷}{0,\cdots ,0}},\stackrel{d-w}{\stackrel{︷}{1,\cdots ,1}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}}),$

$z=(\stackrel{2w-d}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{\frac{3d}{2}-2w}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{\frac{3d}{2}-2w}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{\frac{3d}{2}-2w}{\stackrel{︷}{0,\cdots ,0}},\stackrel{\frac{3d}{2}-2w}{\stackrel{︷}{1,\cdots ,1}},\stackrel{n+2w-3d}{\stackrel{︷}{0,\cdots ,0}}),$

满足任意两点间距离都小于等于d。故 $\left|M\cap H_2\right|\ge 3$。因此， $\left|M\cap Q_n^{\left(d-1,w\right)}\right|\ge 4$。

因为 $u^0\in H_1$，所以点 $s,t,r\in M\cap H_2$。令 $p_1=\left|\left\{i|s_i=t_i=1,1\le i\le w\right\}\right|$，$p_2=\left|\left\{j|s_j=t_j=1,w+1\le j\le n\right\}\right|$，$a=\left|\left\{j|s_j=t_j=0,w+1\le i\le n\right\}\right|$，$k_1=\left|\left\{i|s_i=1,w+1\le i\le n\right\}\right|-p_2$，$k_1=\left|\left\{i|t_i=1,w+1\le i\le n\right\}\right|-p_2$ 且 $\left|s\cap t\right|=p$。则 $p=p_1+p_2$，$0\le p_1\le w-\frac{d}{2}$，$p_2+k_1\ge \frac{d}{2}$，$p_2+k_2\ge \frac{d}{2}$，$a_3=n-w-p_2-k_1-k_2$ 且 $d_H\left(s,t\right)=2\left(w-p\right)\ge d$。故 $k_1,k_2\ge d-w$，且 $a\le n-\frac{3d}{2}$。此时可得 $c+c_3=a\le n-\frac{3d}{2}$。

点r满足 $d_H\left(r,s\right)\ge d$，$d_H\left(r,t\right)\ge d$，故 $\left|r\cap s\right|<w-\frac{d}{2}$，$\left|r\cap t\right|<w-\frac{d}{2}$，那么 ${\displaystyle {\sum }_i{r}_i}\le w-\frac{d}{2}$，${\displaystyle {\sum }_j{r}_j}\le w-\frac{d}{2}$，其中 $i=\left\{w+1\le k\le n|s_k=1,t_k\ne 1\right\}$，$j=\left\{w+1\le k\le n|t_k=1,s_k\ne 1\right\}$。故 $c_1,c_2\le w-\frac{d}{2}$。设 $b=\left\{j|r_j=1,1\le i\le w\right\}$，则 $c\le a-\left[w-\left(b+c_1+c_2\right)\right]\le n+2w-3d$。

定理3.2：对于 $n,d,w\in {\text{Z}}^{+}$，d为偶数，如果 $\frac{2n+2}{5}\le d\le \frac{3n-2}{5}$，$\frac{3d-n}{2}\le w\le \frac{5d-n-1}{5}$ 或 $\frac{6n-5d+1}{5}\le w\le \frac{3n-3d}{2}$，则 $A\left(n,d,w\right)=4$。

证明：因为 $A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)$，我们只需证明在题目所给条件下 $\alpha \left(Q_n^{\left(d-1,w\right)}\right)=4$。由定理2.6(ii)，我们有 $A\left(n,d,w\right)=A\left(n,d,n-w\right)$。所以我们只需证明当 $\frac{2n+2}{5}\le d\le \frac{3n-2}{5}$，$\frac{3d-n}{2}\le w\le \frac{5d-n-1}{5}$ 时， $A\left(n,d,w\right)=4$。此时 $\frac{d}{2}\le w\le \frac{3d}{4}$，且 $n\ge 3d-2w$，满足引理3.1条件，所以可以得到 $\left|M\cap Q_n^{\left(d-1,w\right)}\right|\ge 4$，不妨设 $u_0,s,t,r\in M$，$c_1=\left|\left\{j|s_j=r_j=1,t_j=0,w+1\le j\le n\right\}\right|$，$c_2=\left|\left\{j|t_j=r_j=1,s_j=0,w+1\le j\le n\right\}\right|$，$c_3=\left|\left\{j|r_j=1,w+1\le j\le n\right\}\right|-c_1-c_2$，$c=\left|\left\{j|s_j=t_j=r_j=0,w+1\le j\le n\right\}\right|$。此时由引理3.1可得 $c_1,c_2\le w-\frac{d}{2}$，$c+c_3\le n-\frac{3d}{2}$，$c\le n+2w-3d$。

假设存在点 $m\in M\cap V\left(Q_n^{\left(d-1,w\right)}\right)-\left\{u_0,s,t,r\right\}$，设 $b=\left\{j|m_j=1,1\le j\le w\right\}$。则 $d_H\left(s,m\right)\ge d$，$d_H\left(t,m\right)\ge d$，且 $\left|s\cap m\right|\le w-\frac{d}{2}$，$\left|t\cap m\right|\le w-\frac{d}{2}$。那么 ${\displaystyle {\sum }_i{m}_i}\le w-\frac{d}{2}$，${\displaystyle {\sum }_j{m}_j}\le w-\frac{d}{2}$，其中 $i=\left\{w+1\le k\le n|s_k=1,t_k\ne 1\right\}$，$j=\left\{w+1\le k\le n|t_k=1,s_k\ne 1\right\}$。因为 $\frac{3d}{2}-2w\ge w-\frac{d}{2}$，则b可以取到 $w-\frac{d}{2}$，故 $d_H\left(r,m\right)\le b+\left(w-\frac{d}{2}\right)+c_1+\left(w-\frac{d}{2}\right)+c_2+\left(w-\frac{d}{2}\right)+\left[c_3-\left(\frac{3d}{2}-2w-c\right)\right]+c\le 2n+10w-9d\le d-2$。这与M是 $Q_n^{\left(d-1,w\right)}$ 的独立集矛盾。因此， $\left|M\cap Q_n^{\left(d-1,w\right)}\right|=4$，即 $A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)=4$。

定理3.3：对于 $n,d,w\in {\text{Z}}^{+}$，d为偶数，如果 $\frac{2d+1}{3}\le w\le \frac{3d}{4}$，$n-w+1\le d\le \frac{n+2w}{3}$，或 $\frac{11d-8}{12}\le w\le d-1$，$\frac{4n-4w}{3}\le d\le \frac{3n-3w-1}{2}$，则 $A\left(n,d,w\right)=4$。

证明：因为 $A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)$，我们只需证明在题目所给条件下 $\alpha \left(Q_n^{\left(d-1,w\right)}\right)=4$。由定理2.6(ii)，我们有 $A\left(n,d,w\right)=A\left(n,d,n-w\right)$。所以我们只需证明当 $\frac{2d+1}{3}\le w\le \frac{3d}{4}$，$n-w+1\le d\le \frac{n+2w}{3}$ 时， $A\left(n,d,w\right)=4$。此时 $\frac{d}{2}\le w\le \frac{3d}{4}$，且 $n\ge 3d-2w$，满足引理3.1 条件，所以可以得到 $\left|M\cap Q_n^{\left(d-1,w\right)}\right|\ge 4$，不妨设 $u_0,s,t,r\in M$，$c_1=\left|\left\{j|s_j=r_j=1,t_j=0,w+1\le j\le n\right\}\right|$，$c_2=\left|\left\{j|t_j=r_j=1,s_j=0,w+1\le j\le n\right\}\right|$，$c_3=\left|\left\{j|r_j=1,w+1\le j\le n\right\}\right|-c_1-c_2$，$c=\left|\left\{j|s_j=t_j=r_j=0,w+1\le j\le n\right\}\right|$。此时由引理3.1可得 $c_1,c_2\le w-\frac{d}{2}$，$c+c_3\le n-\frac{3d}{2}$，$c\le n+2w-3d$。

假设存在点 $m\in M\cap H_2-\left\{s,t,r\right\}$，则 $d_H\left(s,m\right)\ge d$，$d_H\left(t,m\right)\ge d$，且 $\left|s\cap m\right|\le w-\frac{d}{2}$。那么 ${\displaystyle {\sum }_i{m}_i}\le w-\frac{d}{2}$，其中 $i=\left\{w+1\le k\le n|s_k=1,t_k\ne 1\right\}$。因为 $0\le \frac{3d}{2}-2w\le w-\frac{d}{2}-1$，则 ${\displaystyle {\sum }_l{m}_l}\le \frac{3d}{2}-2w$ 中 $l=\left\{w+1\le k\le n|r_k=1,s_k,t_k\ne 1\right\}$，故此时 $\begin{array}{l}{d}_H\left(s,m\right)\le \left(\frac{3d}{2}-2w\right)+\left(w-\frac{d}{2}-p\right)+\left(3w-2d\right)+\left(w-\frac{d}{2}\right)+\left(\frac{3d}{2}-2w\right)\\ +\left[\left(w-\frac{d}{2}\right)-\left(3w-2d-c\right)\right]+\left(\frac{3d}{2}-2w\right)+c\le d-2\end{array}$。这与M是 $Q_n^{\left(d-1,w\right)}$ 的独立集矛盾。因此， $\left|M\cap Q_n^{\left(d-1,w\right)}\right|=4$，即 $A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)=4$。

定理3.4：对于 $n,d,w\in {\text{Z}}^{+}$，d为偶数，如果 $n=\frac{3d}{2}+1$，$d=\frac{4w-2}{3}$，则 $A\left(n,d,w\right)=4$。

证明：因为 $A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)$，我们只需证明在题目所给条件下 $\alpha \left(Q_n^{\left(d-1,w\right)}\right)=4$。令 $H_1=D_0^w{{\displaystyle \cap }}^{\text{}}{D}_2^w\cap \cdots \cap D_{d-2}^w$，$H_2=D_d^w\cap D_{d+2}^w\cap \cdots \cap D_{2w}^w$，则 $V\left(Q_n^{\left(d-1,w\right)}\right)=H_1\cap H_2$。不妨设 $u^0\in M$，则对任意 $x\in H_1$ 且 $x\ne u^0$，有 $d_H\left(x,u^0\right)\le d-2<d$。因此， $M\cap H_1=u^0$。

由已知条件可知，至少存在三个点

$x=(\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}},\stackrel{\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}}),$

$y=(\stackrel{w-\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{w-\frac{d}{2}-1}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{w-\frac{d}{2}-1}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}-1}{\stackrel{︷}{1,\cdots ,1}},0),$

$z=(1,\stackrel{\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}-1}{\stackrel{︷}{1,\cdots ,1}},1,\stackrel{w-\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}},\stackrel{\frac{d}{2}-1}{\stackrel{︷}{1,\cdots ,1}}),$

满足任意两点间距离都小于等于d。故 $\left|M\cap H_2\right|\ge 3$。因此， $\left|M\cap Q_n^{\left(d-1,w\right)}\right|\ge 4$。

不妨设 $u_0,s,t,r\in M$，因为 $u^0\in H_1$，所以点 $s,t,r\in M\cap H_2$。设 $\left|s\cap t\right|=p$，我们有 $d_H\left(s,t\right)=2\left(w-k\right)\ge d$，故 $k\le w-\frac{d}{2}$。令 $p_1=\left|\left\{i|s_i=t_i=1,1\le i\le w\right\}\right|$，$p_2=\left|\left\{j|s_j=t_j=1,w+1\le j\le n\right\}\right|$，$a=\left|\left\{j|s_j=t_j=0,w+1\le j\le n\right\}\right|$，$k_1=\left|\left\{i|s_i=1,w+1\le i\le n\right\}\right|-p_2$，$k_2=\left|\left\{i|t_i=1,w+1\le i\le n\right\}\right|-p_2$。则 $p=p_1+p_2$，$0\le p_1\le w-\frac{d}{2}$，$p_2+k_1\ge \frac{d}{2}$，$p_2+k_2\ge \frac{d}{2}$，$a=n-w-p_2-k_1-k_2$。故 $k_1,k_2\ge d-w$，且 $a\le n-\frac{3d}{2}=1$。

情形1. a = 1。

此时有 $p_2=w-\frac{d}{2}$，$k_1,k_2=d-w$，且s和t一定满足在前w个坐标中有 $w-\frac{d}{2}$ 个坐标为1。不妨设

$s=(\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}},\stackrel{\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}}),$

$t=(\stackrel{w-\frac{d}{2}}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{w-\frac{d}{2}-1}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}}{\stackrel{︷}{1,\cdots ,1}},\stackrel{w-\frac{d}{2}-1}{\stackrel{︷}{0,\cdots ,0}},\stackrel{w-\frac{d}{2}-1}{\stackrel{︷}{1,\cdots ,1}},0),$

点r满足 $d_H\left(r,s\right)\ge d$，$d_H\left(r,t\right)\ge d$，故 $\left|r\cap s\right|\le w-\frac{d}{2}$，$\left|r\cap t\right|\le w-\frac{d}{2}$。此时r在前w个坐标中至少有 $w-\frac{d}{2}-1$ 个坐标为1，且只能在 $s_i=t_i=0\left(1\le i\le w\right)$ 的位置i上。因为 $w-2\left(w-\frac{d}{2}\right)=w-\frac{d}{2}-1$，所以在 $s_i=0\left(w+1\le i\le n\right)$ 的位置i上或者在 $t_i=0\left(w+1\le i\le n\right)$ 的位置i上都有 $r_i=1$，不妨设在 $s_i=0\left(w+1\le i\le n\right)$ 的位置i上 $r_i=1$。

假设存在点 $m\in M\cap H_2-\left\{s,t,r\right\}$，则 $d_H\left(s,m\right)\ge d$，$d_H\left(t,m\right)\ge d$，$d_H\left(r,m\right)\ge d$，且 $\left|s\cap m\right|\le w-\frac{d}{2}$，$\left|t\cap m\right|\le w-\frac{d}{2}$。同理可得，m在前w个坐标中至少有 $w-\frac{d}{2}-1$ 个坐标为1，且只能在 $s_i=t_i=0\left(1\le i\le w\right)$ 的位置i上。此时 $d_H\left(m,r\right)\le 2w-d=\frac{d}{2}+1\le d$，矛盾。因此， $\left|M\cap H_2\right|\le 3$。

情形2. a = 0。

点r满足 $d_H\left(r,s\right)\ge d$，$d_H\left(r,t\right)\ge d$，故 $\left|r\cap s\right|\le w-\frac{d}{2}$，$\left|r\cap t\right|\le w-\frac{d}{2}$。因为 $a=0$，所以在 $s_i=0\left(w+1\le i\le n\right)$ 的位置i上有 $t_i=1$，在 $s_i=0\left(w+1\le i\le n\right)$ 的位置i上和在 $t_i=0\left(w+1\le i\le n\right)$ 的位置i上有 $r_i=1$。此时 $p_2=w-\frac{d}{2}-1$ 或者 $w-\frac{d}{2}$，故 $p_1=1$ 或者0。

当 $p_2=w-\frac{d}{2}-1$ 时，s和t在前w个位置分别有 $w-\frac{d}{2}$ 个位置是1。此时r在前w个位置有 $w-\frac{d}{2}-1$ 个位置是1。则 $s_i=t_i=r_i=0\left(1\le i\le w\right)$ 的位置只有一个。假设存在点 $m\in M\cap H_2-\left\{s,t,r\right\}$，则 $d_H\left(s,m\right)\ge d$，$d_H\left(t,m\right)\ge d$，$d_H\left(r,m\right)\ge d$，且 $\left|s\cap m\right|\le w-\frac{d}{2}$，$\left|t\cap m\right|\le w-\frac{d}{2}$，$\left|r\cap m\right|\le w-\frac{d}{2}$。因为 $a=0$，在 $s_i=0,t_i=0,r_i=0\left(w+1\le i\le n\right)$ 的位置i上有 $m_i=1$。此时 $\left|r\cap m\right|>w-\frac{d}{2}$，矛盾。因此， $\left|M\cap H_2\right|\le 3$。

同理，当 $p_2=w-\frac{d}{2}$ 时，也能得到 $\left|r\cap m\right|>w-\frac{d}{2}$，矛盾。因此， $\left|M\cap H_2\right|\le 3$。

综上所述， $\left|M\cap H_2\right|=3$，即 $A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)=4$。

由定理2.6，可以得到以下推论。

推论3.5：对于 $n,d,w\in {\text{Z}}^{+}$，d 为奇数，如果 $\frac{2n+7}{5}\le d\le \frac{3n+3}{5}$，$\frac{3d-n+3}{2}\le w\le \frac{5d-n+4}{5}$ 或 $\frac{6n-5d-4}{5}\le w\le \frac{3n-3d-3}{2}$，则 $A\left(n,d,w\right)=4$。

推论3.6：对于 $n,d,w\in {\text{Z}}^{+}$，d为奇数，如果 $\frac{2d+3}{3}\le w\le \frac{3d+3}{4}$，$n-w\le d\le \frac{n+2w-3}{3}$，或者 $\frac{11d+3}{12}\le w\le d$，$\frac{4n-4w-3}{3}\le d\le \frac{3n-3w-3}{2}$，则 $A\left(n,d,w\right)=4$。

4. 结论

本文将 $A\left(n,d,w\right)$ 看作是维超立方体d-1次幂图中所有重量为w的点导出子图 $Q_n^{\left(d-1,w\right)}$ 的最大独立集的大小，通过构造最大独立集的方法得到了：对于 $n,d,w\in {\text{Z}}^{+}$，d为偶数，如果 $\frac{2n+2}{5}\le d\le \frac{3n-2}{5}$，$\frac{3d-n}{2}\le w\le \frac{5d-n-1}{5}$ 或 $\frac{6n-5d+1}{5}\le w\le \frac{3n-3d}{2}$，则 $A\left(n,d,w\right)=4$ ；如果 $\frac{2d+1}{3}\le w\le \frac{3d}{4}$，$n-w+1\le d\le \frac{n+2w}{3}$，或 $\frac{11d-8}{12}\le w\le d-1$，$\frac{4n-4w}{3}\le d\le \frac{3n-3w-1}{2}$，则 $A\left(n,d,w\right)=4$ ；如果 $n=\frac{3d}{2}+1$，$d=\frac{4w-2}{3}$，则 $A\left(n,d,w\right)=4$。

文章引用

师娟娟,杨卫华. 超立方体幂图中常重点集导出子图的一类独立集
A Class of Independent Sets of Subgraphs Derived from Constant Focus Sets in Hypercube Power Graphs[J]. 应用数学进展, 2022, 11(03): 1170-1177. https://doi.org/10.12677/AAM.2022.113126

参考文献