1980年, Erdös, Harary和Klawe引入残差图^[1]的概念, 他们研究了完备残差图, 对于任意正整数$m$和$n$, 证明了$(m+1)K_{n}$是唯一的具有最小阶$(m+1)n$的$m-K_{n}$ -残差图, 同时证明了$C_{5}$是唯一的具有最小阶5的连通的$K_{2}$ -残差图.当$n>1$, 且$n\neq2$时, 连通的$K_{n}$ -残差图的最小阶为$2(n+1)$; 当$n\neq2, 3, 4$时, $K_{n+1}\times$$K_{2}$是唯一的具有最小奇阶的连通的$K_{n}$ -残差图.对于残差图性质的研究国内外也有不少的研究成果^[2-10], 文献[2]讨论了奇阶完备残差图的一些性质和结论, 并构造了一些奇阶完备残差图; 文献[3]研究了二重$K_{n}$ -残差图, 并得到当$n>3$时, 二重$K_{n}$ -残差图的最小阶并构造了极图.文献[4]研究了三重$K_{n}$ -残差图, 当$n<11$时的最小阶, 并构造了极图; 文献[5]研究了三重$K_{n}$ -残差图, 当$n\geq11$时的最小阶和极图.残差图的概念的提出也对计算机网络和信息方面有重要的意义, 文献[6-7]主要讨论的是残差图的应用. Erdös等人提出的残差图是定义在平面上的残差图, 残差图的定义还可以推广到超平面上^[8-9]; 文献[8]得到3维超平面完备残差图的最小阶和唯一极图; 文献[9]得到3维超平面完备图与$K_{t}$合成残差图的最小阶和唯一极图.本文主要是把残差图推广到任意维超平面上, 并得到任意维超平面完备残差图的最小阶为$(n_{1}+1)(n_{2}+1)\cdots(n_{r}+1)$, 并构造了唯一的任意维超平面完备残差图, 同时得到任意维超平面完备残差图关于图的加法的重要性质, 最后得到多重任意维超平面完备残差图的最小阶为$(n_{1}+m)(n_{2}+m)\cdots(n_{r}+m)$, 并得到唯一的多重任意维超平面完备残差图.

定义2.1  设图$G=(V, E)$, $u\in$$V=V(G)$, 集合$N(u)=\{x|x\in$$V(G), x $与$u$邻接$\}$与$N^{*}(u)=\{u\}\cup$$N(u)$分别叫做顶点$u$的邻域和闭邻域.

定义2.2  设$F$是一个给定的图, 如果对每一个顶点$u\in V(G)$, 从$G$中减去$u$的闭邻域$N^{*}(u)$得到的图与$F$同构^[10-11], 则称图$G$为$F$ -残差图.递归地, 定义$G$是$m-F$ -残差图为, 如果对于任意$u\in V(G)$, $G-N^{*}(u)$得到的图都是$(m-1)-F$ -残差图.当然$1-F$ -残差图简单地叫做$F$ -残差图.

定义2.3  图$G$是$r-1$维超平面完备图, 如果$x\in V(G)$, $V(G)=V_{1}\times V_{2}\times \cdots\times V_{r}$, 其中$x=\{(x_{1}, x_{2}, \cdots, x_{r})|x_{i}\in V_{i}, i=1, 2, \cdots, r\}$, $|V_{i}|=n_{i}, i=1, 2, \cdots, r$, 两个顶点$x=(x_{1}, x_{2}, \cdots, x_{r})$和$y=(y_{1}, y_{2}, \cdots, y_{r})$相邻当且仅当$x\neq y$, 存在某个$k=1, 2, \cdots, r$, $x_{k}=y_{k}$.为方便起见, 本文用$HPK(n_{1}, n_{2}, \cdots, n_{r})$代替$r-1$维超平面完备图.

定义2.4  设$G_{1}=(V_{1}, E_{1})$, $G_{2}=(V_{2}, E_{2})$是两个图, $G_{1}$与$G_{2}$合成$G=G_{1}[G_{2}]$, 定义为$V(G)=V_{1}\times$$V_{2}=\{x=(x_{1}, x_{2})|(x_{1}\in$$V_{1}, x_{2}\in$$V_{2}\}$, 两个顶点$u=(u_{1}, u_{2})$和$v=(v_{1}, v_{2})$是相邻的当且仅当$u_{1}$与$v_{1}$在$G_{1}$相邻, 或者$u_{1}=v_{1}$, $u_{2}$与$v_{2}$在$G_{2}$中相邻.

定义2.5  令$G=(V, E)$, $S\subset V=V(G)$, 若$S$不存在两个点$x, y\in S$在$G$中邻接, 而且$|S|=k$, 则称$S$为$G$中的$k$ -独立集.

定义2.6  设图$G_{1}=(V_{1}, E_{1})$, $G_{2}=(V_{2}, E_{2})$, 定义$G=G_{1}+G_{2}$, 其中$V(G)=V_{1}\cup$$V_{2}$, $E(G)=E_{1}\cup$$E_{2}$$\cup E[K(V_{1}, V_{2})]$, 这里$K(V_{1}, V_{2})$是以$V_{1}$与$V_{2}$为独立点集的完备二部图.

下面是文献[1]中的一个重要结论.

引理2.1^[1]  设$G$是$F$ -残差图, 则$d(u)=\nu(G)-\nu(F)-1$, $\forall$$u\in$$V(G)$, 其中$\nu(G)$是$G$的阶.

文中没有定义的术语与符号参阅文献[1-8].

由定义2.3可以直接得到下面引理.

引理3.1  若$G$是$HPK(n_{1}, n_{2}, \cdots n_{r})$ -残差图, $n_{1}, n_{2}, \cdots n_{r}\geq r\geq3$, 则对任意两点$u, v\in V(G)$, 存在一点$w\in G$, 使得$u, v\in V(G)-N^{*}(w)$.

对于任意维超平面残差图还有以下结论.

引理3.2  若$G\cong HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1), n_{1}, $ $n_{2}, \cdots, n_{r}\geq1, r\geq2, $则$G$是$HPK(n_{1}, $ $n_{2}, \cdots, n_{r})$ -残差图.

证  令$V(G)=V_{1}\times V_{2}\times \cdots \times V_{r}$, $|V_{i}|=n_{i}+1$, 点$x=(x_{1}, x_{2}, \cdots x_{r})$与$y=(y_{1}, y_{2}, \cdots, y_{r})$彼此不相邻, 定义为$x_{i}\neq y_{i}$, $i=1, 2, \cdots, r$, 因此对于任意一点$v=(v_{1}, v_{2}, \cdots, v_{r})\in G$, 则有

$ G_{1}=G-N^{*}(v)\\ \ \ \ \ \ =\langle(x_{1}, x_{2}, \cdots, x_{r})|x_{i}\in V_{i}, x_{i}\neq v_{i}, i=1, 2, \cdots, r\rangle\\ \ \ \ \ \ =\langle V_{1}^{'}\times V_{2}^{'}\times \cdots V_{r}^{'}\rangle, $

其中$V_{i}^{'}=V_{i}-\{v_{i}\}\subset V_{i}, i=1, 2, \cdots, r$, 点$x=(x_{1}, x_{2}, \cdots, x_{r})\in G_{1}$与$y=(y_{1}, y_{2}, \cdots, y_{r})\in G_{1}$, 且有$G_{1}\subset G$, 同时两点的邻接关系与在$G$中邻接关系相同, 因此$G_{1}\cong HPK(n_{1}, n_{2}, \cdots, n_{r})$, 由残差图的定义可知$G$是$HPK(n_{1}, $ $n_{2}, \cdots , n_{r})$ -残差图.证毕.

引理3.3  若$G=HPK(n_{1}, n_{2}, \cdots n_{r})$, $\{v_{1}, v_{2}, \cdots, v_{r}, v_{0}\}$是$G$的$r+1$独立集, 则有

$ N^{*}(v_{1})\cap N^{*}(v_{2})\cap \cdots \cap N^{*}(v_{r})\cap N^{*}(v_{0})=\phi. $

证  假设存在点$x=(x_{1}, x_{2}, \cdots, x_{r})\in N^{*}(v_{1})\cap N^{*}(v_{2})\cap \cdots \cap N^{*}(v_{r})\cap N^{*}(v_{0})$, 并且与$v_{k}=(v_{1}^{k}, v_{2}^{k}, \cdots, v_{r}^{k}), k=0, 1, \cdots, r$邻接, 由$G$的邻接条件可知, 存在一点$x_{i_{k}}=v_{i_{k}}^{k}$, 所以有$1\leq i_{k}\leq r, k=0, 1, \cdots, r$, $i_{k}=i_{l}=h$, $k\neq l$, 则一定存在$k, l$, 使得$v_{h}^{k}=v_{h}^{l}=x_{h}$, 然而$v_{h}^{k}$与$v_{h}^{l}$在$G$中不邻接, 从而导致矛盾.证毕.

引理3.4  若$H=HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1)$, $\{v, v_{1}, v_{2}, \cdots, v_{r}\}$是$H$的$(r+1)$ -独立集, 且设$H_{i}=H-N^{*}(v_{i}), i=1, 2, \cdots, r$, 则有

$ N^{*}(v)=N_{H_{1}}^{*}(v)\cup (N_{H_{2}}^{*}(v))\cap N_{H_{2}}^{*}(v_{1})\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cup\cdots\cup(N_{H_{k}}^{*}(v)\cap N_{H_{k}}^{*}(v_{1})\cap\cdots\cap N_{H_{k}}^{*}(v_{k-1}))\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cup\cdots\cup(N_{H_{r}}^{*}(v)\cap N_{H_{r}}^{*}(v_{1})\cap\cdots\cap N_{H_{r}}^{*}(v_{r-1})). $

证  因为$V(H)=V(H_{i})\cup N^{*}(v_{i}), v\in V(H_{i})$, 所以

$ \ \ \ \ N^{*}(v)=N^{*}(v)\cap V(H)=N^{*}(v)\cap(V(H_{1})\cup N^{*}(v_{1}))\\ =(N^{*}(v)\cap V(H_{1}) )\cup(N^{*}(v)\cap (N^{*}(v_{1})) =(N_{H_{1}}^{*}(v)\cup(N^{*}(v)\cap (N^{*}(v_{1})) $

和

$ \ \ \ \ N^{*}(v)\cap N^{*}(v_{1})\cap\cdots\cap N^{*}(v_{i})\\ =(N^{*}_{H_{i+1}}(v)\cap (N^{*}_{H_{i+1}}(v_{1})\cap\cdots\cap N^{*}_{H_{i+1}}(v_{i}))\\ \ \ \ \ \cup (N^{*}(v)\cap N^{*}(v_{1})\cap\cdots\cap N^{*}(v_{i})\cap N^{*}(v_{i+1})), i=1, 2\cdots, r. $

引理3.5  如果$G\cong H\cong HPK(n_{1}, n_{2}, \cdots n_{r})$, $\{v_{1}, v_{2}, \cdots, v_{k}\}\subset V(G)$, 以及$\{u_{1}, u_{2}, \cdots, $ $ u_{k}\}\subset V(H)$分别是$G$和$H$的$k$ -独立集, 则有

$ |N_{G}^{*}(v_{1})\cap N_{G}^{*}(v_{2})\cap\cdots\cap N_{G}^{*}(v_{k})|=|N_{H}^{*}(v_{1})\cap N_{H}^{*}(v_{2})\cap\cdots\cap N_{H}^{*}(v_{k})|. $

证  对于任意$k$ -独立集$\{v_{1}, v_{2}, \cdots, v_{k}\}\subset V(G)$, 这里把$G$的所有$k$ -独立集定义为一个函数, 记为$g_{k}$, 又假设$g_{k}=g(v_{1}, v_{2}, \cdots, v_{k})=|N^{*}(v_{1})\cap N^{*}(v_{2})\cap\cdots\cap N^{*}(v_{k})|$, 则$g_{k}$是一个常值函数, 因为当$k=1$时,

$ g_{1}=g(v)=|N^{*}(v)|=\nu(G)-\nu(G-N^{*}(v))=n_{1}n_{2}\cdots n_{r}-(n_{1}-1)(n_{2}-1)\cdots (n_{r}-1), $

所以$g_{1}=g(v)$为一个常数.类似地, 可以证明$g_{k}$是一个常数, 且由引理3.3可得知当$1<k<r+1$时, $g_{k}=0$.设$G_{k}=G-N^{*}(v_{1})-N^{*}(v_{2})-\cdots-N^{*}(v_{k})$, 则有$G_{k}\cong HPK(n_{1}-k, n_{2}-k, \cdots, n_{r}-k)$和$\nu(G_{k})=(n_{1}-k)(n_{2}-k)\cdots(n_{r}-k)=v_{k}$, 因此有

$ \ \ \ \ |N^{*}(v_{1})\cup N^{*}(v_{2})\cup\cdots\cup N^{*}(v_{k})|\\ ={\displaystyle\sum^{k}_{i=1}}g(v_{i})-{\displaystyle\sum_{1\leq i<j\leq k}}g(v_{i}, v_{j})+\cdots+(-1)^{l-1}\\ \ \ \ \ {\displaystyle\sum_{1\leq i_{1}<i_{2}<\cdots<i_{l}\leq k}}g(v_{i_{1}}, v_{i_{2}}, \cdots, v_{i_{l}})+\cdots+(-1)^{k-1} g(v_{1}, v_{2}, \cdots, v_{k})\\ =\nu(G)-\nu(G_{k})=v-v_{k}. $

又由于$G\cong H$, 则存在一个映射$\sigma:V(H)\rightarrow V(G)$, $u_{1}$和$u_{2}$在$H$中邻接当且仅当$\sigma(u_{1})$和$\sigma(u_{2})$在$G$中彼此邻接.假设$v_{i}=\sigma(u_{i}), i=1, 2, \cdots, r$, 则有$\{v_{1}, v_{2}, \cdots, v_{k}\}\subset V(G)$是一个$k$ -独立集当且仅当$\{u_{1}, u_{2}, \cdots, u_{k}\}\subset V(H)$是$k$ -独立集, 因此

$ |N_{G}^{*}(v_{1})\cap N_{G}^{*}(v_{2})\cap\cdots N_{G}^{*}(v_{k})|=|N_{H}^{*}(u_{1})\cap N_{H}^{*}(u_{2})\cap\cdots N_{H}^{*}(u_{k})|. $

定理3.1  若$ G$是一个$HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, $n_{1}, n_{2}, \cdots, n_{r}\geq r\geq 3$, 则有$\nu(G)\geq(n_{1}+1)(n_{2}+1)\cdots(n_{r}+1)$.

证  对于任意一点$v\in G$, 有$G-N^{*}(v)=F\cong HPK(n_{1}, n_{2}, \cdots, n_{r})$, 记

$ V(F)=\{(x_{1}, x_{2}, \cdots, x_{r})|1\leq x_{i}\leq n_{i}, i=1, 2, \cdots, r\}, $

点$x=(x_{1}, x_{2}, \cdots, x_{r})$和$y=(y_{1}, y_{2}, \cdots, y_{r})$在$ F$中彼此不邻接定义为当且仅当$x_{i}\neq y_{i}, i=1, 2, \cdots, r$.设$v_{k}=(k, k, \cdots, k), k=1, 2, \cdots, r$, 则有$\{v, v_{1}, v_{2}, \cdots, v_{r}\}$是$G$中的$r+1$ -独立集.由引理3.4与3.5可知

$ F_{i}=G-N^{*}(v_{i})\cong HPK(n_{1}, n_{2}, \cdots, n_{r}), i=1, 2, \cdots, r. $

因此

$ N^{*}(v)=N^{*}_{F_{1}}(v)\cup(N^{*}_{F_{2}}(v)\cap N^{*}_{F_{2}}(v_{1}))\cup \cdots \cup(N^{*}_{F_{k}}(v)\cap N^{*}_{F_{k}}(v_{1})\cap\cdots\cap N^{*}_{F_{k}}(v_{k-1}))\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cup \cdots \cup(N^{*}_{F_{r}}(v)\cap N^{*}_{F_{r}}(v_{1})\cap\cdots\cap N^{*}_{F_{r}}(v_{r-1}))\cup (N^{*}(v)\cap N^{*}(v_{1})\cap \cdots\cap N^{*}(v_{r})). $

下面设$H=HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1)$, 则有

$ |N^{*}(v)|=|N^{*}_{F_{1}}(v)|+|N^{*}_{F_{2}}(v)\cap N^{*}_{F_{2}}(v_{1})|+\cdots+|(N^{*}_{F_{k}}(v)\cap N^{*}_{F_{k}}(v_{1})\cap\cdots\cap N^{*}_{F_{k}}(v_{k-1})|\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +\cdots+|(N^{*}_{F_{r}}(v)\cap N^{*}_{F_{r}}(v_{1})\cap\cdots\cap N^{*}_{F_{r}}(v_{k-1})|+|N^{*}(v)\cap N^{*}(v_{1})\cap \cdots\cap N^{*}(v_{r})|\\ \ \ \ \ \ \ \ \ \ \ \ \ =|N^{*}_{H}(u)|+|N^{*}(v)\cap N^{*}(v_{1})\cap \cdots\cap N^{*}(v_{r})|, $

因此有

$ \nu(G)=\nu(F)+|N^{*}_{G}(v)|=\nu(F)+|N^{*}_{H}(u)|+|N^{*}(v)\cap N^{*}(v_{1})\cap\cdots\cap N^{*}(v_{r})|\\ \ \ \ \ \ \ \ \ \geq n_{1}n_{2}\cdots n_{r}+(n_{1}+1)(n_{2}+1)\cdots (n_{r}+1)-n_{1}n_{2}\cdots n_{r}\\ \ \ \ \ \ \ \ \ =(n_{1}+1)(n_{2}+1)\cdots (n_{r}+1). $

证毕.

上面得到$r-1$维超平面残差图的最小阶, 下面主要构造最小图, 并证明此图是唯一的极图.为了得到极图, 设$ G$是一个$HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, $n_{1}, n_{2}, \cdots, n_{r}\geq r\geq 3$, 主要任务是命名$ G$中点的名称以及点与点的邻接关系以及相应的命名规则.首先定义$G$中的点和邻接关系, 设

$ V(G)=V_{1}\times V_{2}\times\cdots\times V_{r}=\{(x_{1}, x_{2}, \cdots, x_{r})|0\leq x_{i}\leq n_{i}, i=1, 2, \cdots, r\}. $

定义点$x=(x_{1}, x_{2}, \cdots, x_{r})$与$y=(y_{1}, y_{2}, \cdots, y_{r})$彼此不相邻当且仅当$x_{i}\neq y_{i}, i=1, 2, \cdots, r$.对任意一点$u\in G$, 则有$G-N^{*}(u)=H\cong HPK(n_{1}, n_{2}, \cdots, n_{r})$.下面定义$H$中的点

$ V(H)=\{(x_{1}, x_{2}, \cdots, x_{r})|1\leq x_{i}\leq n_{i}, i=1, 2, \cdots, r\}, $

(3.1)

在$H$中定义两点不相邻与在$G$中的定义一致, 由此可以根据(3.1) 式定义$G$的任何一个子集.又由于$H=G-N^{*}(v)$, 要命名$G$中的点, 首先命名$N^{*}(v)$中的点.设$v_{k}=(k, k, \cdots, k), k=1, 2, \cdots, r$, 则有

$ H_{k}=G-N^{*}(v_{k})\cong HPK(n_{1}, n_{2}, \cdots, n_{r}), k=1, 2, \cdots, r. $

由引理3.4可得

$ N^{*}(v)=N^{*}_{H_{1}}(v)\cup(N^{*}_{H_{2}}(v)\cap N^{*}_{H_{2}}(v_{1}))\cup \cdots \cup(N^{*}_{H_{k}}(v)\cap N^{*}_{H_{k}}(v_{1})\cap\cdots\cap N^{*}_{H_{k}}(v_{k-1}))\nonumber\\ \cup \cdots \cup(N^{*}_{H_{r}}(v)\cap N^{*}_{H_{r}}(v_{1})\cap\cdots\cap N^{*}_{H_{r}}(v_{r-1}))\cup (N^{*}(v)\cap N^{*}(v_{1})\cap \cdots\cap N^{*}(v_{r})). $

(3.2)

再根据引理3.5可知

$ |N^{*}(v)|=\nu(G)-\nu(H)=(n_{1}+1)(n_{2}+1)\cdots(n_{r}+1)-n_{1}n_{2}\cdots n_{r}. $

再由引理3.3知$N^{*}(v)\cap N^{*}(v_{1})\cap \cdots\cap N^{*}(v_{r})=\phi$, 所以(3.2) 式最后一个并集的集合为空集, 所以(3.2) 式应为

$ N^{*}(v)=N^{*}_{H_{1}}(v)\cup(N^{*}_{H_{2}}(v)\cap N^{*}_{H_{2}}(v_{1}))\cup \cdots \cup(N^{*}_{H_{k}}(v)\cap N^{*}_{H_{k}}(v_{1})\cap\cdots\cap N^{*}_{H_{k}}(v_{k-1}))\nonumber\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cup \cdots \cup(N^{*}_{H_{r}}(v)\cap N^{*}_{H_{r}}(v_{1})\cap\cdots\cap N^{*}_{H_{r}}(v_{r-1}). $

(3.3)

为了命名$G$中的所有点, 因为$H=G-N^{*}(v)$以及$H_{k}=G-N^{*}(v_{k})$, 故下面先命名$N^{*}(v_{k})$命名规则, 设$H=HPK(n_{1}, n_{2}, \cdots, n_{r})$, $n_{1}, n_{2}, \cdots, n_{r}\geq r\geq3$,

$ V(H)=\{(x_{1}, x_{2}, \cdots, x_{r})|1\leq x_{i}\leq n_{i}, i=1, 2, \cdots, r\}, $

点$x=(x_{1}, x_{2}, \cdots, x_{r})$与$y=(y_{1}, y_{2}, \cdots, y_{r})$不相邻定义为当且仅当$x_{i}\neq y_{i}, i=1, 2, \cdots, r$.设$v=v_{1}=(1, 1, \cdots, 1)$,

$ F_{1}=H-N^{*}(v_{1})=\langle(x_{1}, x_{2}, \cdots, x_{r})|2\leq x_{i}\leq n_{i}, i=1, 2, \cdots, r \rangle, $

则有下面命名规则.

命名规则3.1   $R_{1}:i_{1}, i_{2}, \cdots, i_{l}, i_{l+1}, \cdots, i_{r}$是$\{1, 2, \cdots, r\}$的一个排列, 其中$1\leq i_{1}<i_{2}<\cdots<i_{l}\leq r$, $1\leq i_{l+1}<\cdots<i_{r}\leq r, 1\leq l\leq r-1$.

$R_{2}:a_{1}, a_{2}, \cdots, a_{l}$是一个序列, 其中$2\leq a_{k}\leq n_{i_{k}}, k=1, 2, \cdots, l$.

$R_{3}:Y=\{(y_{1}, y_{2}, \cdots, y_{r})\in F_{1}|y_{i_{r}}\neq a_{k}, k=1, 2, \cdots, l\}$.

$R_{4}:b_{1}, b_{2}, \cdots, b_{r}$是一个序列, 其中$1\leq b_{k}\leq n_{i_{k}}, b_{k}\neq a_{k}, k=1, 2, \cdots, l$.

$R_{5}:u_{k}=(u_{1}^{k}, u_{2}^{k}, \cdots, u_{r}^{k}), k=1, 2, \cdots, l$, 其中$u_{i_{k}}^{k}=a_{k}, u_{i_{t}}^{k}=b_{t}, 1\leq t\leq l, t\neq k, u_{i_{l+1}}^{k}=\cdots=u_{i_{r}}^{k}=2$, 则有唯一点$x^{*}\in N_{F}^{*}(v)$, 满足

$R_{6}:x^{*}$是与$u_{1}, u_{2}, \cdots, u_{l}$邻接的.

$R_{7}:x^{*}$与$Y$中的点彼此不邻接.

下面说明命名规则3.1合理性, 设$x^{*}=(x_{1}, x_{2}, \cdots, x_{r})$, $x_{i_{k}}=a_{k}, k=1, 2, \cdots, l, x_{i_{l+1}}=\cdots=x_{i_{r}}=1$, 这里点$x^{*}$是满足$C_{6}$和$C_{7}$这两条性质的, 且这样的$x^{*}$是唯一的, 因为$x^{*}$与$Y$中点是彼此不邻接的, 因此有$x_{i_{l+1}}=\cdots=x_{i_{r}}=1$.

下面需要证明的是$x_{i_{k}}=a_{k}$, $x^{*}$是不邻接$y\in Y$, $x_{i_{k}}$仅仅只能为$a_{k}$或者1, 而这里$x_{i_{k}}\neq b_{k}$, 故有$x^{*}$与$u_{k}$邻接的, 以及$x_{i_{k}}=a_{k}, k=1, 2, \cdots, l$, 命题规则是合理的.

检验$N^{*}(v_{1})$的点的关键条件是命名规则3.1中$R_{1}$, $R_{2}$, $R_{3}$, 由于$b_{1}, b_{2}, \cdots, b_{l}$选择是不唯一的, 导致$u_{1}, u_{2}, \cdots, u_{l}$也是不唯一的, 所以命名的关键主要是$R_{1}$, $R_{2}$, $R_{3}$, 因此这三个条件可以作为整个图$G$的命名条件, 于是得到下面的命名规则.

命名规则3.2  命名规则3.1中的$R_{1}$, $R_{2}$, $R_{3}$可以唯一确定$ N(v_{1})$中的每一个点, 相反$ N^{*}(v_{1})$中的所有的点如果都已经确定, 则命名规则3.1中$R_{1}$, $R_{2}$, $R_{3}$也相应被确定.

命名规则3.2的前部分可直接由命名规则3.1的说明得到, 下面说明结论的后半部分.

设$x=(x_{1}, x_{2}, \cdots, x_{r})\in N(v_{1})$, 根据$N(v_{1})$的点的性质, 可以重新命名规则3.1中的$R_{1}$, $R_{2}$, $R_{3}$.

$R_{1}:$ $i_{1}, i_{2}, \cdots, i_{l}, i_{l+1}, \cdots, i_{r}$, $1\leq i_{1}<i_{2}<\cdots<i_{l}\leq r$, $1\leq i_{l+1}<\cdots<i_{r}\leq r, 1\leq l\leq r-1$, 其中$x_{i_{l+1}}=\cdots=x_{i_{r}}=1$, $x_{i_{1}}, x_{i_{2}}, \cdots, x_{i_{1}}\neq1$.

$R_{2}:$ $a_{1}, a_{2}, \cdots, a_{l}$是一个排列, 其中$a_{k}=x_{i_{k}}$, $2\leq a_{k}\leq n_{i_{k}}, k=1, 2, \cdots, l$.

$R_{3}:$ $Y=\{(y_{1}, y_{2}, \cdots, y_{r})\in F_{1}|y_{i_{k}}\neq a_{k}, k=1, 2, \cdots, l\}$.

由此可以根据命名规则3.1和3.2命名所有的$N^{*}(v_{k})$中的点, 其中$v_{k}=(k, k, \cdots, k), k=1, 2, \cdots, r$.如果有$N_{H}(v)$的点$x$未命名, 其中$H=HPK(n_{1}, n_{2}, \cdots, n_{r})$, $n_{1}, n_{2}, \cdots, n_{r}\geq r\geq 3$, 则可以任意找一点$v\in H$, 根据$H-N^{*}(v)$中的点的命名规则命名, 即可以根据命名规则3.1和3.2命名.对于$N(v)$中点的命名可以根据$N^{*}(v)$的点命名, 只须设$v=(0, 0, \cdots, 0)$, 所以$N(v)$的点的命名规则也被确定.

因为$H=G-N*(v)$, 以及$H_{k}=G-N^{*}(v_{k})$, 要确定$G$中的点, 最后剩下$N_{H_{k}}(v)$中的点没有命名规则, 由式子(3.1), (3.3) 可知首先命名$N_{H_{1}}(v)$中的点, 有下面的命名规则.

命名规则3.3  只需要把命名规则3.1和3.2中的1用0代替即可得到$N_{H_{1}}(v)$中的点的命名规则.

因为$H=G-N^{*}(v_{1}), v_{1}=(1, 1, \cdots, 1)$, $V(H_{1})=\{(x_{1}, x_{2}, \cdots, x_{r})|0\leq x_{i}\leq n_{i}, x_{i}\neq1\}$. $N_{H_{1}}(v)$中的点可以根据

$ V(H_{1})-N^{*}(v)=V(H)-N^{*}(v_{1})=G-N^{*}(v)-N^{*}(v_{1}) $

的点命名, 即根据$H=G-N^{*}(v)$的点命名规则命名, 只须把命名规则3.1和3.2中的1用0代替即可.

下面命名$N_{H_{2}}(v)\cap N_{H_{2}}(v_{1})$的点.由于

$ H_{2}=G-N^{*}(v_{2})\cong HPK(n_{1}, n_{2}, \cdots, n_{r}), v_{2}=(2, 2, \cdots, 2), \\ H-N^{*}(v_{k})=G-N^{*}(v)-N^{*}(v_{k})=H_{k}-N^{*}(v)=F_{k}, \\ V(H_{2})=\{(x_{1}, x_{2}, \cdots, x_{r})|0\leq x_{i}\leq n_{i}, x_{i}\neq2, i=1, 2, \cdots, r\}, $

为了命名$N_{H_{2}}^{*}(v)\cap N_{H_{2}}^{*}(v_{1})$中的点, 可以根据$V(H_{2})-N_{H_{2}}^{*}(v)=V(H)-N_{H}^{*}(v_{2})$中的点命名, 首先说明$H_{2}$中点的命名规则.

命名规则3.4  $R_{1}:$ $i_{1}, i_{2}, \cdots, i_{l}, i_{l+1}, \cdots, i_{r}$一个排列.

$R_{2}:$ $a_{1}, a_{2}, \cdots, a_{l}$是一个序列, 其中$1\leq a_{k}\leq n_{i_{k}}, a_{k}\neq2, k=1, 2, \cdots, l, 1\in\{a_{1}, a_{2}, $ $\cdots, a_{l}\}$.

$R_{3}:$ $Y=\{(y_{1}, y_{2}, \cdots, y_{r})\in F_{2}|y_{i_{k}}\neq a_{k}, k=1, 2, \cdots, l\}$.

命名规则3.4只在命名规则3.2的$R_{2}$增加了条件$1\in\{a_{1}, a_{2}, \cdots, a_{l}\}$, 增加此条件的目的主要是保证条件$R_{1}$, $R_{2}$, $R_{3}$确定的点$x$一定是属于$N_{H_{2}}^{*}(v)\cap N_{H_{2}}^{*}(v_{1})$.如果不增加此条件, 根据图$G$的点的命名的唯一性原则, 只能确定$N_{H_{2}}^{*}(v)$中的点$x$, 增加此条件后在$N_{H_{2}}^{*}(v)\cap N_{H_{2}}^{*}(v_{1})$找一点$x^{*}$, 而点$x^{*}$可以分别在$H_{1}$与$H_{2}$重新命名.

下面主要说明$x^{*}$在$H_{1}$与$H_{2}$的命名是一致的, 前面命名规则3.4命名了$H_{2}$中的点.下面先完成$H_{1}$中的命名规则: $x^{*}$在$H_{1}$命名为$(x_{1}, x_{2}, \cdots, x_{r})$.又由于$x^{*}$不邻接$v_{2}=(2, 2, \cdots, 2)\in H_{1}$, 因此在$H_{1}$中的命名规则可以如下.

命名规则3.5  $R_{1}:$ $i_{1}, i_{2}, \cdots, i_{l}, i_{l+1}, \cdots, i_{r}$是一个排列, 其中$x_{i_{1}}, x_{i_{2}}, \cdots, x_{i_{l}}\neq0, 1, 2$, $x_{i_{l+1}}=\cdots=x_{i_{l}}=0$.

$R_{2}:$ $ a_{1}, a_{2}, \cdots, a_{l}$是一个序列, 其中$ a_{k}= x_{i_{k}}\neq0, 1, 2, k=1, 2, \cdots, l$.

$R_{3}:$ $Y=\{(y_{1}, y_{2}, \cdots, y_{r})\in F_{2}|y_{i_{k}}\neq a_{k}, k=1, 2, \cdots, l\}$.

下面说明$x^{*}$在$H_{1}$与$H_{2}$中命名是一致的, 假设在$H_{2}$中有一点$x^{**}=(x_{1}^{'}x_{2}^{'}\cdots x_{r}^{'})$, 其中$x_{i_{k}}^{'}=a_{k}, k=1, 2, \cdots, l$以及$x_{i_{l+1}}^{'}=\cdots=x_{i_{l}}^{'}=0$且$a_{k}\neq0, 1, 2$, 因此$x^{**}$是与点$v_{1}=(1, 1, \cdots, 1)\in H_{2}$不邻接的, 而$x^{**}\in (N_{H_{1}}^{*}(v)\cap N_{H_{2}}^{*}(v))$, 从而$x^{**}=x^{*}$, 故$x^{*}$在$H_{1}$与$H_{2}$中命名是一致的.

以上完成了$N_{H_{2}}^{*}(v)\cap N_{H_{2}}^{*}(v_{1})$中的点命名, 对于$N_{H_{k}}^{*}(v)\cap N_{H_{k}}^{*}(v_{1})\cap\cdots\cap N_{H_{k}}^{*}(v_{k-1})$的点的命名与$N_{H_{2}}^{*}(v)\cap N_{H_{2}}^{*}(v_{1})$中点的命名规则类似, 只须在命名规则3.5的$R_{2}$与$R_{3}$改为以下规则即可.

命名规则3.6  $R_{1}:$ $i_{1}, i_{2}, \cdots, i_{l}, i_{l+1}, \cdots, i_{r}$是一个排列, 其中$x_{i_{1}}, x_{i_{2}}, \cdots, x_{i_{l}}\neq0, 1, 2$, $x_{i_{l+1}}=\cdots=x_{i_{l}}=0$.

$R_{2}:$ $ a_{1}, a_{2}, \cdots, a_{l}$是一个序列, 其中$1\leq a_{t}\leq n_{i_{t}}, a_{t}\neq k, $以及$\{1, 2, \cdots, k-1\}\subset \{a_{1}, a_{2}, \cdots, a_{k}\}$.

$R_{3}:$ $ Y=\{(y_{1}, y_{2}, \cdots, y_{r})\in F_{k}|y_{i_{t}}\neq a_{t}, t=1, 2, \cdots, l\}$.

根据上面的命名规则可以确定$x^{*}=(x_{1}, x_{2}, \cdots, x_{r})$, 且$x^{*}\in N_{H_{k}}^{*}(v)\cap N_{H_{k}}^{*}(v_{1})\cap\cdots\cap N_{H_{k}}^{*}(v_{k-1})$, 由上面的结论, 可设$k=r$, 则可以得到式子(3.3) 的最后一个式子$N_{H_{r}}^{*}(v)\cap N_{H_{r}}^{*}(v_{1})\cap\cdots\cap N_{H_{r}}^{*}(v_{r-1})$命名规则.

命名规则3.7  $R_{1}:$ $i_{1}, i_{2}, \cdots, i_{r-1}, i_{r}$是一个排列, 且有$1\leq i_{1}<i_{2}<\cdots<i_{r-1}\leq r$, $1\leq i_{r}\leq r$.

$R_{2}:$ $ a_{1}, a_{2}, \cdots, a_{r-1}$是一个序列, 其中$\{a_{1}, a_{2}, \cdots, a_{r-1}\}=\{1, 2, \cdots, r-1\}$.

$R_{3}:$ $ Y=\{(y_{1}, y_{2}, \cdots, y_{r})\in F_{r}|y_{i_{k}}\neq a_{k}, k=1, 2, \cdots, r-1\}$.

根据上面的命名规则$R_{1}$, $R_{2}$, $R_{3}$, 可以完全命名$H_{r}$, 这里$H_{r}=G-N^{*}(v_{k})$, 前面定义了$N^{*}(v_{k})$的命名规则, 这样$G$中的所有的点被$H_{r}$与$N^{*}(v_{k})$点完全决定, 可以命名为$V(G)=\{(x_{1}, x_{2}, \cdots, x_{r})|0\leq x_{i}\leq n_{i}\}$, $G$中的两点$x=(x_{1}, x_{2}, \cdots, x_{r})$和$y=(y_{1}, y_{2}, \cdots, y_{r})$彼此不邻接当且仅当$x_{i}\neq y_{i}, i=1, 2, \cdots, r$.

根据上面的命名原则可以得到下面结论.

定理3.2  若$G$是$HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, $n_{1}, n_{2}, \cdots, n_{r}\geq r\geq 3$, $\nu(G)=(n_{1}+1)(n_{2}+1)\cdots(n_{r}+1)$, 则$G\cong HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1)$, 且这样的$G$是唯一的.

证  对于$G$中任意两点$x$和$y$, 根据引理3.1可知, 一定存在一点$w$, 使得$w$与$x$和$y$都不邻接.假设$w\in H_{k}$, 其中$ H_{k}$是遵循上面的命名规则, 对于任意一个$k$, 如果既有$x\in H_{k}$也有$y \in H_{k}$, 则可以使用$H_{k}$命名规则来命名.设$H^{*}=G-N^{*}(w)\cong HPK(n_{1}, n_{2}, \cdots n_{r})$, 则有$x, y\in H^{*}$.因为$G$中的点可根据$H_{k}$中的点命名规则命名, 又根据命名的唯一性可以命名$G$中所有的点, 因为$H^{*}=G-N^{*}(w)$, 所以根据$G$命名规则命名$H^{*}$的点, 事实上$x, y\in H^{*}=G-N^{*}(w)$, 根据命名规则可知, $x=(x_{1}, x_{2}, \cdots, x_{r})$和$y=(y_{1}, y_{2}, \cdots, y_{r})$是彼此不邻接的, 故$G$中任意两点都彼此不邻接, 所以$G\cong HPK(n_{1}+1, n_{2}+1, \cdots n_{r}+1)$, 再由点的邻接关系$HPK(n_{1}+1, n_{2}+1, \cdots n_{r}+1)$是唯一最小的$r-1$维超平面完备残差图.

这一节主要是讨论任意维超平面完备残差图的结构, 主要有下面的结果.

定理4.1  若$G$是$HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, $n_{1}, n_{2}, \cdots, n_{r}\geq r+2\geq5$, 则有$\nu(G)=k(n_{1}+1)(n_{2}+1)\cdots(n_{r}+1)$, $G=G_{1}+G_{2}+\cdots+G_{k}$, 且$G_{i}\cong HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1), i=1, 2, \cdots, k$.

为了证明此定理, 先定义有关超平面的点独立集的坐标变换.

定义4.1  如果$H=HPK(n_{1}, n_{2}, \cdots, n_{r})$, $V(H)=\{(x_{1}, x_{2}, \cdots, x_{r})|1\leq x_{i}\leq n_{i}, i=1, 2, \cdots, r\}$, 假设独立集$S_{1}=\{v_{1}, v_{2}, \cdots, v_{r}, v_{0}\}$与$S_{2}=\{u_{1}, u_{2}, \cdots, u_{r}, u_{0}\}$, 且$S_{1}$与$S_{2}$都是$(r+1)$ -独立集. $S_{2}$与$S_{1}$坐标变换定义如下, 如果$u_{i}=v_{i}, i=0, 1, 2, \cdots, r;i\neq k, l$, 其中$u_{i}=(u_{1}^{i}, u_{2}^{i}, \cdots, u_{r}^{i})$, $v_{i}=(v_{1}^{i}, v_{2}^{i}, \cdots, v_{r}^{i})$, $i=0, 1, 2, \cdots, r$, 使得$u_{j}^{k}=v_{j}^{k}$或者$v_{j}^{l}$或者$x_{j}$, $u_{j}^{l}=v_{j}^{l}$或者$v_{j}^{k}$或者$y_{j}, j=1, 2, \cdots, r$, $x_{j}, y_{j}\neq v_{j}^{i}, i=0, 1, 2, \cdots, r$, 则有$u_{j}^{k}\neq u_{j}^{l}$.

由定义4.1, 可以直接得到下面引理.

引理4.1  如果$H=HPK(n_{1}, n_{2}, \cdots, n_{r})$, $V(H)=\{(x_{1}, x_{2}, \cdots, x_{r})|1\leq x_{i}\leq n_{i}, i=1, 2, \cdots, r\}$, $n_{1}, n_{2}, \cdots n_{r}\geq r+1\geq4$, 则对任意$u\in H$, 存在一个$(r+1)$ -独立集$\{u_{1}, u_{2}, \cdots, u_{r}, $ $u\}$, 可以和任何一个$(r+1)$ -独立集$\{v_{1}, v_{2}, \cdots, v_{r}, v\}$进行坐标变换.

下面证明定理4.1.

设$v_{0}, v_{1}, \cdots, v_{r}$是图$G$中的$r+1$独立集.若$H_{i}=G-N^{*}(v_{i})\cong HPK(n_{1}, n_{2}, $ $\cdots, n_{r}), i=0, 1, \cdots, r$.设$G_{1}=<H_{0}\cup H_{1}\cup H_{2}\cup\cdots\cup H_{r}>$, 假设$G_{1}\subset G$是$G$中由$H_{0}, H_{1}, \cdots, H_{r}$生成的最小子图, 显然, $v_{i}\notin H_{i}$, 以及$v_{i}\in H_{j}, i, j=0, 1, 2, \cdots, r, i\neq j$. $N^{*}(v_{i})\cap V(H_{i})=\phi, i=0, 1, 2, \cdots, r$, 因此有

$ H_{i}=H_{i}-N^{*}(v_{i})\subset G_{1}-N^{*}(v_{i})\subset G-N^{*}(v_{i})=H_{i}, i=0, 1, 2, \cdots, r, \\ H_{i}= G_{1}-N^{*}(v_{i})=G_{1}-N^{*}_{G_{1}}(v_{i}), i=0, 1, 2, \cdots, r. $

下证$G_{1}\cong HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1)$, 因为$G_{1}-N^{*}(v_{i})=H_{i}\cong HPK(n_{1}, n_{2}, \cdots, n_{r})$, 则有

$ N_{G_{1}}^{*}(v_{0})=N_{H_{1}}^{*}(v_{0})\cup(N_{H_{2}}^{*}(v_{0})\cap N_{H_{2}}^{*}(v_{1}))\cup \cdots \cup(N^{*}_{H_{k}}(v_{0})\cap N^{*}_{H_{k}}(v_{1})\cap\cdots\cap N^{*}_{H_{k}}(v_{k-1}))\\ \cup \cdots \cup(N^{*}_{H_{r}}(v_{0})\cap N^{*}_{H_{r}}(v_{1})\cap\cdots\cap N^{*}_{H_{r}}(v_{r-1}))\cup (N_{G_{1}}^{*}(v_{0})\cap N_{G_{1}}^{*}(v_{1})\cap \cdots\cap N_{G_{1}}^{*}(v_{r})) $

以及

$ N_{G_{1}}^{*}(v_{0})\cap N_{G_{1}}^{*}(v_{1})\cap \cdots\cap N_{G_{1}}^{*}(v_{r})=V(G_{1})\cap N^{*}(v_{0})\cap N^{*}(v_{1})\cap\cdots\cap N^{*}(v_{r})\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ={\displaystyle\bigcup ^{r}_{i=0}}(V(H_{i}))\cap(N^{*}(v_{0})\cap\cdots\cap N^{*}(v_{r}))=\phi, $

再由引理3.4和引理3.5可知

$ \nu(G_{1})=(n_{1}+1)(n_{2}+1)\cdots (n_{r}+1). $

如果$G_{1}=G$, 再根据定理3.2知, $G$是最小阶的$HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图.如果$G_{1}\neq G$, 设$N^{*}(v_{0})\cap N^{*}(v_{1})\cap\cdots\cap N^{*}(v_{r})=W$, 则有$W\neq\phi$以及$G_{1}=G-W$, 并且$V(G_{1})\cap W=\phi$, 因此$V(G_{1})\subseteq V(G)-W$.对于任意$x\in V(G)-W$, 有$x\notin W$, 以及$x\notin N^{*}(v_{i})$, 对任意的$i$, 有$x\in G-N^{*}(v_{i})=H_{i}\subset G_{1}$, 所以$V(G)-W\subseteq V(G_{1})$, 以及$G_{1}=G-W$, 故有$G_{1}$是$HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图.

由上面证明可知任意的$x\in G_{1}$都与任意$w\in W$邻接.下面证明对于任意的$x\in H_{0}$, $x$都与任意的$w\in W$邻接的.因为$H_{0}=G-N^{*}(v_{0})$, 所以有$\{v_{1}, v_{2}, \cdots, v_{r}\}\subset V(H_{0})$, 由条件可知$v\in H_{0}$以及$\{v_{1}, v_{2}, \cdots, v_{r}, v\}$是$H_{0}$的$(r+1)$ -独立集, 且$v$也是与任意的$w\in W$邻接的, 若不然, $v$不与$w^{*}\in W$邻接, 则有

$ H=G-N^{*}(v)\cong HPK(n_{1}, n_{2}, \cdots, n_{r}) $

以及$\{v_{0}, v_{1}, \cdots, v_{r}\}\subset V(H)$是$H$ $(r+1)$ -独立集, 因此存在$w^{*}\in H$, 即$w^{*}\in N_{H}^{*}(v_{0})\cap N_{H}^{*}(v_{1})\cap\cdots\cap N_{H}^{*}(v_{r})\neq \phi$, 这与引理3.2矛盾, 故有$W\subset N^{*}(v)$.

因为$n_{1}, n_{2}, \cdots, n_{r}\geq r+2\geq5$, 因此存在两点$u, v\in H_{0}$, 使得$\{v_{1}, v_{2}, \cdots, v_{r}, u, $ $v\}$ $\subset V(H)$是$(r+2)$ -独立集, 则$W\subset N^{*}(u)\cap N^{*}(v)$.现在假设$\{v_{1}^{'}, v_{2}^{'}, v_{3}, v_{4}$ $\cdots, u, v\} $是$(r+2)$ -独立集, 则$H_{0}$中存在另一点$\{v_{1}, v_{2}, \cdots, v_{r}, u, v\}$与之进行坐标变换.根据上面的讨论同样可得$W\subset N^{*}(v_{1}^{'})\cap N^{*}(v_{2}^{'})$, 再由引理3.1可知对任意$x\in H_{0}$, 以及$x\in G_{1}$, 都有$x$是与任意$w\in W$邻接的, 因此有

$ G_{1}-N_{G_{1}}^{*}(x)=(G-W)-N_{G_{1}}^{*}(x)=G-(W\cup N_{G_{1}}^{*}(x))\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =G-N^{*}(x)\cong HPK(n_{1}, n_{2}, \cdots, n_{r}), \forall x\in G_{1}. $

下面证明$G_{1}$是$HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图.由于$\nu(G)=(n_{1}+1)(n_{2}+1)\cdots (n_{r}+1)$, 根据定理3.2, 有$G\cong HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1)$.又因为任意$w\in W$, 则有$V(G_{1})\subset N^{*}(w)$.设$<W>=F$, 则有$G=G_{1}+F$以及

$ G-N^{*}(w)=G-(N_{F}^{*}(w)\cup V(G_{1}))=G-V(G_{1})-N_{F}^{*}(w)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =F-N_{F}^{*}(w)\cong HPK(n_{1}, n_{2}, \cdots, n_{r}), $

由于$w\in W$的任意性, $F$是$HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, 所以对$F$可以类似的讨论, $G_{2}\subseteq F$的一个最小子图, 则$G_{2}\cong HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1), F=G_{2}+F_{1}, $其中$F_{1}=F-V(G_{2})$.重复前面在$G$中的讨论, 则有

$ G=G_{1}+G_{2}+\cdots+G_{k}, G_{i}\cong HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1), i=1, 2, \cdots, k. $

根据多重超平面残差图的定义容易得到引理5.1和5.2.

引理5.1  若$G=(V, E)$, $\{v_{0}, v_{1}, \cdots, v_{r}\}\in G\subset V(G)$是$G$中$(k+1)$ -独立集, 则有

$ N^{*}(v_{1})\cap N^{*}(v_{2})\cap\cdots \cap N^{*}(v_{k})= (N^{*}_{F}(v_{1})\cap N^{*}_{F}(v_{2})\cap\cdots\cap N^{*}_{F}(v_{k}))\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cup(N^{*}(v_{1})\cap N^{*}(v_{2})\cap\cdots \cap N^{*}(v_{k})\cap N^{*}(v_{0})), $

其中$F=G-N^{*}(v_{0})$.

引理5.2  令$G=(V, E)$, $u_{1}, u_{2}, \cdots, u_{k}\in G$, $\{v_{0}, v_{1}, \cdots, v_{r}\}\subset V(G)$是$G$中$(r+1)$ -独立集, 对每一个$v_{i}$都不与$u_{j}$邻接.令$F_{i}=G-N^{*}(v_{i}), i=1, 2, \cdots, l $, 则有

$ N^{*}(u_{1})\cap N^{*}(u_{2})\cap\cdots \cap N^{*}(u_{k})= (N^{*}_{F_{1}}(u_{1})\cap N^{*}_{F_{1}}(u_{2})\cap\cdots\cap N^{*}_{F_{1}}(u_{k}))\cup(N^{*}_{F_{2}}(u_{1})\\ \cap N^{*}_{F_{2}}(u_{2})\cap\cdots\cap N^{*}_{F_{2}}(u_{k})\cap N^{*}_{F_{2}}(v_{1}))\cup\cdots\cup (N^{*}_{F_{l}}(u_{1})\cap N^{*}_{F_{l}}(u_{2})\cap\cdots\cap N^{*}_{F_{l}}(u_{k})\cap N^{*}_{F_{l}}(v_{1})\\ \cap\cdots\cap N^{*}_{F_{l}}(v_{l-1}))\cup N^{*}(u_{1})\cap N^{*}(u_{2})\cap\cdots \cap N^{*}(u_{k})\cap N^{*}(v_{1})\cap\cdots \cap N^{*}(v_{l}). $

由任意维超平面残差图的性质也可以得到$m$重任意维超平面残差图的性质.

引理5.3  若$G$是$HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, $H=HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1), n_{1}, n_{2}, $ $\cdots, n_{r}\geq r\geq 3$.令$\{v_{1}, v_{2}, \cdots, v_{k}\}\subset V(G)$以及$\{u_{1}, u_{2}, \cdots, $ $u_{k}\}\subset V(H)$分别是$G$和$H$中的$k$ -独立集, 则有

$ |N^{*}_{G}(v_{1})\cap N^{*}_{G}(v_{2})\cap\cdots\cap N^{*}_{G}(v_{k})|\geq|N^{*}_{H}(u_{1})\cap N^{*}_{H}(u_{2})\cap\cdots\cap N^{*}_{H}(u_{k})|. $

证  当$k\geq r+1$, 由引理3.3可知

$ N^{*}_{H}(u_{1})\cap N^{*}_{H}(u_{2})\cap\cdots\cap N^{*}_{H}(u_{k})=\phi, $

则上面不等式成立.下面假设$1\leq k\leq r$, 则存在$v\in G$和$u\in H$, 且有$\{v_{1}, v_{2}, \cdots, v_{k}, v\}$ $\{u_{1}, u_{2}, \cdots, u_{k}, u\}$分别是$G$和$H$中$(k+1)$ -独立集.设$G_{1}=G-N^{*}(v)$, $H_{1}=H-N^{*}(u)$, 则有$G_{1}\cong H_{1}\cong HPK(n_{1}, n_{2}, \cdots, n_{r})$, $\{v_{1}, v_{2}, \cdots, v_{k}\}\subset V(G_{1})$以及$\{u_{1}, u_{2}, \cdots, u_{k}\}\subset V(H_{1})$分别是$G_{1}$和$H_{1}$的$k$ -独立集, 且有

$ |N^{*}_{G}(v_{1})\cap N^{*}_{G}(v_{2})\cap\cdots\cap N^{*}_{G}(v_{k})|=|N^{*}_{G_{1}}(v_{1})\cap N^{*}_{G_{1}}(v_{2})\cap\cdots\cap N^{*}_{G_{1}}(v_{k})|\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +|N^{*}_{G}(v_{1})\cap\cdots\cap N^{*}_{G}(v_{k}) \cap N^{*}_{G}(v)|, \\ |N^{*}_{H}(u_{1})\cap N^{*}_{H}(u_{2})\cap\cdots\cap N^{*}_{H}(u_{k})|=|N^{*}_{H_{1}}(u_{1})\cap N^{*}_{H_{1}}(u_{2})\cap\cdots\cap N^{*}_{H_{1}}(u_{k})|\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +|N^{*}_{H}(u_{1})\cap\cdots\cap N^{*}_{H}(u_{k}) \cap N^{*}_{H}(u)|. $

因为$G_{1}\cong H_{1}\cong HPK(n_{1}, n_{2}, \cdots, n_{r})$, 由引理3.4知

$ |N^{*}_{G_{1}}(v_{1})\cap\cdots\cap N^{*}_{G_{1}}(v_{k})|=|N^{*}_{H_{1}}(u_{1})\cap\cdots\cap N^{*}_{H_{1}}(u_{k})|, $

由此可知当$k\geq r+1$, $k=r, r-1, \cdots, 3, 2, 1$.上面不定式成立的.

引理5.4  假设$G$是$2-HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, $H=HPK(n_{1}$ $+2, n_{2}+2, \cdots , n_{r}+2), n_{1}, n_{2}, \cdots, n_{r}\geq r\geq 3$ $\{v_{1}, v_{2}, \cdots, v_{k}\}\subset V(G)$和$\{u_{1}, u_{2}, \cdots, u_{k}$ $\}\subset V(H)$分别是$G$和$H$的$k$ -独立集, 则有

$ |N^{*}_{G}(v_{1})\cap N^{*}_{G}(v_{2})\cap\cdots\cap N^{*}_{G}(v_{k})|\geq|N^{*}_{H}(v_{1})\cap N^{*}_{H}(v_{2})\cap\cdots\cap N^{*}_{H}(v_{k})|. $

证  由引理3.3知, $k\geq r+1$不等式是显然成立的, 下面假设$1\leq k\leq r$, 根据引理5.3的讨论, 在$G$和$H$中存在点$v\in G$, $u\in H$, 使得$G_{1}=G-N^{*}(v), H_{1}=H-N^{*}(u)$, 以及$\{v_{1}, v_{2}, \cdots, v_{k}\}\subset V(G_{1})$和$\{u_{1}, u_{2}, \cdots, u_{k}\}\subset V(H_{1})$.因为$G_{1}$是$HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, 以及$H_{1}=HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1)$, 因此当$k\geq r+1$不等式成立, $k=r, r-1, \cdots, 3, 2, 1$.

引理5.5  假设$G$是$m-HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, $H=HPK(n_{1}+m, n_{2}+m, \cdots , n_{r}+m), n_{1}, n_{2}, \cdots, n_{r}\geq r\geq 3$, $\{v_{1}, v_{2}, \cdots, v_{r}\}\subset V(G)$和$\{u_{1}, u_{2}, \cdots, u_{k}\}\subset V(H)$分别是$G$和$H$的$k$ -独立集, 则有$|N^{*}_{G}(v_{1})\cap\cdots\cap N^{*}_{G}(v_{k})|\geq|N^{*}_{H}(u_{1})\cap\cdots\cap N^{*}_{H}(u_{k})|$.

证  当$m=1, 2$, 有引理5.3和引理5.4知成立的.下面对$m$用数学归纳法证明, 假设对$m-1$成立, 由引理3.3可知$k\geq r+1$时, 不等式成立, 讨论与引理5.3, 5.4的讨论一样可以得到, 对于$m$, $k\geq r+1$, $k=r, r-1, \cdots, 3, 2, 1$是成立的.

定理5.1  假设$G$是$m-HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, $n_{1}, n_{2}, \cdots, n_{r}\geq r\geq3$, 则有$\nu(G)\geq (n_{1}+m)(n_{2}+m)\cdots (n_{r}+m)$.

证  当$m=1$, 由定理3.1可知, 结论成立.利用数学归纳法, 假设当$m-1\geq1$成立, 当为$m$时, $G$是$m-HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, $H=HPK(n_{1}+m, n_{2}+m, \cdots, n_{r}+m)$.由引理5.4知, $|N^{*}_{G}(v)|\geq N^{*}_{H}(u)$, 对于$G$和$H$中的任意一点$v\in G$, $u\in H$.设$G_{1}=G-N^{*}(v), H_{1}=H-N^{*}(u)$, 则有$G_{1}$是$(m-1)-HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, 故有

$ H_{1}=HPK(n_{1}+m-1, n_{2}+m-1, \cdots, n_{r}+m-1). $

利用归纳假设有

$ \nu(G)=\nu(G_{1})+|N^{*}_{G}(v)|\geq \nu(H_{1})+|N^{*}_{H}(u)|=\nu(H)=(n_{1}+m)(n_{2}+m)\cdots(n_{r}+m). $

定理5.2  假设$G$是$m-HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, $n_{1}, n_{2}, \cdots, $ $n_{r}\geq r\geq3$, 以及$\nu(G)= (n_{1}+m)(n_{2}+m)\cdots (n_{r}+m)$, 则有$G\cong HPK(n_{1}+m, n_{2}+m, \cdots, n_{r}+m).$

证  设$G$是$m-HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, $H=HPK(n_{1}+m, n_{2}+m, \cdots, n_{r}+m), n_{1}, n_{2}, \cdots, n_{r}\geq r\geq3$, $\nu(G)=\nu(H)$.当$m=1$时, 由定理3.2可知, $G\cong HPK(n_{1}+1, n_{2}+1, \cdots, n_{r}+1)$.利用数学归纳法, 假设$m-1\geq1$成立.对于m, 存在点$v\in G$和$u\in H$, 有$G_{1}=G-N^{*}(v)$是$(m-1)-HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图, 以及$H_{1}=H-N^{*}(u)=HPK(n_{1}+m-1, \cdots, n_{r}+m-1)$.再由引理5.5定理5.1, 有

$ |N^{*}_{G}(v)|\geq|N^{*}_{H}(u)|=\nu(H)-\nu(H_{1}), \nu(G_{1}\geq \nu(H_{1}), \\ \nu(G_{1})=\nu(G)-|N^{*}_{G}(v)|\leq \nu(G)-|N^{*}_{H}(u)|=\nu(H)-|N^{*}_{H}(u)|=\nu(H_{1}), \\ \nu(G_{1})=\nu(H_{1})=(n_{1}+m-1)(n_{2}+m-1)\cdots(n_{r}+m-1), $

因此有$G_{1}$是最小阶的$(m-1)-HPK(n_{1}, n_{2}, \cdots, n_{r})$ -残差图.根据归纳假设有$G_{1}\cong HPK(n_{1}+m-1, n_{2}+m-1, \cdots, n_{r}+m-1)$.由于$v$是$G$中任意一点, 根据定义2.2知, $G$是最小阶的$ HPK(n_{1}+m-1, n_{2}+m-1, \cdots, n_{r}+m-1)$ -残差图, 设$n_{i}^{'}=n_{i}+m-1\geq n_{i}\geq r\geq3, i=1, 2, \cdots, r$, 由定理3.2可知$G\cong HPK(n_{1}+m, n_{2}+m, \cdots, n_{r}+m)$.证毕.