残差图的概念^[1]由Erdös, Harary和Klawe引入的, 他们研究了完备残差图.对于任意正整数$m$和$n$, 证明了$(m+1)K_{n}$是唯一的具有最小阶$(m+1)n$的$m$-$K_{n}$ -残差图, 同时证明了$C_{5}$是唯一的具有最小阶5的连通的$K_{2}$ -残差图.当$1<n\neq2$时, 连通的$K_{n}$ -残差图的最小阶$2(n+1)$; 当$n\neq2, 3, 4$时, $K_{n+1}\times$$K_{2}$是唯一的具有最小奇阶的连通的$K_{n}$ -残差图.对于$m-K_{n}$ -残差图他们提出如下两个猜想^[1].

猜想 1  当$n\neq2$时, 连通$m$-$K_{n}$ -残差图的最小阶为min$\{2n(m+1), (n+m)(m+1)\}$.

猜想 2  当$n$充分大时, 有唯一的具有最小阶$m-K_{n}$ -残差图.

对于残差图的研究国内外已有不少的研究成果^[2-11], 在文[2]中我们证明了对于任意正整数$n$和$k$存在$2(n+k)$阶的$K_{n}$ -残差图.当$n=2, 3, 4$时, 存在$2n+3$阶的$K_{n}$ -残差图.当$n=6$时, $C_{5}[K_{3}]$是唯一的具有最小奇阶15的$K_{6}$ -残差图.文献[3]讨论了奇阶完备残差图, 证明了对于任意奇数$n$不存在奇阶$K_{n}$ -残差图, 并构造了一些奇阶残差完备图.本文主要把Erdös, Harary和Klawe的平面完备残差图推广到3维超平面上, 得到了3维超平面完备残差图最小阶$(n_{1}+1)(n_{2}+1)(n_{3}+1)(n_{4}+1)$以及相应的唯一极图; 同时也得到了$m$重3维超平面完备残差图最小阶为$(n_{1}+m)(n_{2}+m)(n_{3}+m)(n_{4}+m)$和相应的唯一极图.

由文献[1]可得

注 1  设$G$是$F$ -残差图, 则$d(u)=\nu(G)-\nu(F)-1$, $u\in V(G)$, 这里$\nu(G)$是$G$的阶.

定义 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$同构^[12-17], 则称图$G$为$F$ -残差图.递归地定义$G$是$m$-$F$ -残差图, 如果对于任意$u\in V(G)$, $G$-$N^{*}(u)$得到的图都是$(m-1)$-$F$ -残差图, 当然$1$-$F$ -残差图简单地叫做$F$ -残差图.

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

由定义2.2和定义2.3可得, 当$G=HPK(n_{1}, n_{2}, n_{3}, n_{4})$时, 则$n=\nu(G)=n_{1}n_{2}n_{3}n_{4}$; 当其中一个$n_{i}=1$时, $G$就是一个完全图$K_{n}$.事实上$HPK(m, n)=K_{m}\times K_{n}$, $G=HPK(n)=\overline{K_{n}}$是一个顶点数为$n$的空图.

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

引理 2.1  如果$F$是连通图, 但$F$不是完备图, 则不存在不连通的$F$ -残差图.

证  假设$G$是不连通的$F$ -残差图, $G$至少有两个极大的连通分支$G_{1}$, $ G_{2}$.取$u\in V(G_{1})$, 则$V(G_{2})\cap N^{*}(u)=\phi$.于是$ G_{2}$就是$G$-$N^{*}(u)$的一个极大的连通分支.又由$G$-$N^{*}(u)\cong F$连通, 故$G_{2}=G-N^{*}(u)\cong F$.由于$F$不是完备图, 故$G_{2}$中必有二顶点$v$, $w$不邻接, 故$w$不属于$N^{*}(v)$.一方面$G-N^{*}(v)\cong F$连通.

另一方面由$V(G_{1})\cap N^{*}(v)=\phi$, $V(G_{1})\cup\{w\}\subset V(G-N^{*}(v))$, $w$与$V(G_{1})$中的顶点不邻接, 又$G-N^{*}(v)$中有一个极大的连通分支$G_{1}$和一个与$G_{1}$中顶点不邻接的顶点$w$, 从而不连通, 导致矛盾.证毕

引理 2.2  如果$G=HPK(n_{1}, n_{2}, n_{3}, n_{4})$, $\{v_{1}, v_{2}, v_{3}, v_{4}, v_{0}\}$是$G$中5 -独立集, 则

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

证  假设$x=(x_{1}, x_{2}, x_{3}, x_{4})\in N^{*}(v_{1})\cap N^{*}(v_{2})\cap N^{*}(v_{3})\cap N^{*}(v_{4})\cap N^{*}(v_{0})$, 以及$v_{k}=(v_{1}^{k}, v_{2}^{k}, v_{3}^{k}, v_{4}^{k}), k=0, 1, \cdots, 4$, 则$x$与$v_{k}$邻接, 由$G$的邻接条件可知, 存在一个$x_{i}=v_{i}^{k}$, 又因为$1\leq i\leq 4, k=0, 1, \cdots, 4$, $k\neq l$, 则一定存在$v_{h}^{k}=v_{h}^{l}=x_{h}$, 然而$v_{h}^{k}$与$v_{h}^{l}$在$G$中不邻接, 导致矛盾.证毕

引理 2.3  如果$H=HPK(n_{1}+1, n_{2}+1, n_{3}+1, n_{4}+1)$, $\{v, v_{1}, v_{2}, v_{3}, v_{4}\}$是$H$中5 -独立集, 以及$H_{i}=H-N^{*}(v_{i}), $ $i=1, 2, 3, 4$, 则

$ \begin{eqnarray*} N^{*}(v)&\;=&\; N_{H_{1}}^{*}(v)\cup (N_{H_{2}}^{*}(v)\cap N_{H_{2}}^{*}(v_{1})) \cup(N_{H_{3}}^{*}(v)\cap N_{H_{3}}^{*}(v_{1})\cap N_{H_{3}}^{*}(v_{2}))\\ && \cup(N_{H_{4}}^{*}(v)\cap N_{H_{4}}^{*}(v_{1})\cap N_{H_{4}}^{*}(v_{2})\cap N_{H_{4}}^{*}(v_{3}))\\ && \cup (N^*(v))\cap(N^*(v_1))\cap(N^*(v_2))\cap(N^*(v_3))\cap(N^*(v_4)).\end{eqnarray*} $

证  由于$V(H)=V(H_{i})\cup N^{*}(v_{i}), $ $v\in V(H_{i})$.则有

$ \begin{eqnarray*}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})), \end{eqnarray*} $

由此可得

$ \begin{eqnarray*} && N^{*}(v)\cap N^{*}(v_{1})=(V^*_{H_2}(v)\cap V^*_{H_2}(v_1))\cup (N^*(v)\cap N^*(v_1) \cap N^*(v_2)), \\ && N^{*}(v)\cap N^{*}(v_{1})\cap N^{*}(v_{2})=(V^*_{H_3}(v)\cap V^*_{H_3}(v_1)\cap V^*_{H_3}(v_2))\\ && \cup (N^*(v)\cap N^*(v_1) \cap N^*(v_2) \cap N^*(v_3)), \\ && N^{*}(v)\cap N^{*}(v_{1})\cap N^{*}(v_{2}\cap N^{*}(v_{3})=(V^*_{H_4}(v)\cap V^*_{H_4}(v_1)\cap V^*_{H_4}(v_2)\cap V^*_{H_4}(v_3))\\ && \cup (N^*(v)\cap N^*(v_1) \cap N^*(v_2) \cap N^*(v_3)\cap N^*(v_4)).\end{eqnarray*} $

由引理2.2可以得到如下引理

引理 2.4  如果$G\cong H\cong HPK(n_{1}, n_{2}, n_{3}, n_{4})$, $\{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 N_{G}^{*}(v_{k})|=|N_{H}^{*}(v_{1})\cap N_{H}^{*}(v_{2})\cap\cdots 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}$是一个常值函数, $g_{1}=g(v)=|N^{*}(v)|=v(G)-v(G-N^{*}(v))=n_{1}n_{2}n_{3} n_{4}-(n_{1}-1)(n_{2}-1)(n_{3}-1)(n_{4}-1), $所以$g_{1}=g(v)$为一个常数.类似地, 可以证明$g_{k}$是一个常数.根据引理2.2可得$g_{k}=0$, $1<k<5$.令$G_{k}=G-N^{*}(v_{1})-N^{*}(v_{2})-\cdots-N^{*}(v_{k})$, 则有

$ G_{k}=HPK(n_{1}-k, n_{2}-k, n_{3}-k, n_{4}-k) $

和$\nu(G_{k})=(n_{1}-k)(n_{2}-k)(n_{3}-k)(n_{4}-k)=v_{k}$.因此有

$ \begin{eqnarray*}&& |N^{*}(v_{1})\cup N^{*}(v_{2})\cup N^{*}(v_{k})|\\ &=& {\displaystyle\sum^{k}_{i=1}}g(v_{i})-{\displaystyle\sum\limits_{1\leq i<j\leq k}}g(v_{i}, v_{j})+\cdots+(-1)^{l-1}{\displaystyle\sum\limits_{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})=v(G)-v(G_{k})=v-v_{k}.\end{eqnarray*} $

又由于$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, 3, 4$, 则有$\{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})|. $

证毕

定理 2.1  假设$G$是一个$HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图, $n_{1}, n_{2}, n_{3}, n_{4}\geq 4$, 则

$ \nu(G)\geq(n_{1}+1)(n_{2}+1)(n_{3}+1)(n_{4}+1). $

证  对任意的$v\in G$, 令$G-N^{*}(v)=F\cong HPK(n_{1}, n_{2}, n_{3}, n_{4})$,

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

顶点$x=(x_{1}, x_{2}, x_{3}, x_{4})$, $y=(y_{1}, y_{2}, y_{3}, y_{4})$在$F$中彼此不邻接, 当且仅当$x_{i}\neq y_{i}, i=1, 2, 3, 4$.设$v_{k}=(k, k, \cdots, k), $ $k=1, 2, 3, 4$, 则$\{v, v_{1}, v_{2}, v_{3}, v_{4}\}$是$G$中$5$ -独立集.

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

由引理2.3, 2.4, 则有

$ \begin{eqnarray*}N^{*}(v)&\;=&\; N^{*}_{F_{1}}(v)\cup(N^{*}_{F_{2}}(v)\cap N^{*}_{F_{2}}(v_{1}))\cup(N^{*}_{F_{3}}(v)\cap N^{*}_{F_{3}}(v_{1})\cap N^{*}_{F_{3}}(v_{2}))\\ && \cup(N^{*}_{F_{4}}(v)\cap N^{*}_{F_{4}}(v_{1})\cap N^{*}_{F_{4}}(v_{2})\cap N^{*}_{F_{4}}(v_{3}))\\ && \cup (N^{*}(v)\cap N^{*}(v_{1})\cap N^{*}(v_{2})\cap N^{*}(v_{3})\cap N^{*}(v_{4})).\end{eqnarray*} $

假设$H=HPK(n_{1}+1, n_{2}+1, n_{3}+1, n_{4}+1)$, 以及

$ \begin{eqnarray*}|N^{*}(v)|&\;=&\; |N^{*}_{F_{1}}(v)|+|N^{*}_{F_{2}}(v)\cap N^{*}_{F_{2}}(v_{1})|+|N^{*}_{F_{3}}(v)\cap N^{*}_{F_{3}}(v_{1})\cap N^{*}_{F_{3}}(v_{2})|\\ && +|N^{*}_{F_{4}}(v)\cap N^{*}_{F_{4}}(v_{1})\cap N^{*}_{F_{4}}(v_{2})\cap N^{*}_{F_{4}}(v_{3})|\\ &&+|N^{*}(v)\cap N^{*}(v_{1})\cap N^{*}(v_{3})\cap N^{*}(v_{4})|\\ &\;=&\; |N^{*}_{H}(u)|+|N^{*}(v)\cap N^{*}(v_{1})\cap N^{*}(v_{2})\cap N^{*}(v_{3})\cap N^{*}(v_{4})|. \end{eqnarray*} $

因此

$ \begin{eqnarray*}\nu(G)&\;=&\;\nu(F)+|N^{*}(v)|=\nu(F)+|N^{*}_{H}(u)|\\ &&+|N^{*}(v)\cap N^{*}(v_{1})\cap N^{*}(v_{2})\cap N^{*}(v_{3})\cap N^{*}(v_{4})|\\ &\;\geq&\;n_{1}n_{2} n_{3}n_{4}+(n_{1}+1)(n_{2}+1)(n_{3}+1)(n_{4}+1)-n_{1}n_{2} n_{3}n_{4}\\ &\;=&\;(n_{1}+1)(n_{2}+1)(n_{3}+1)(n_{4}+1).\end{eqnarray*} $

定理 2.2  假设$G$是一个$HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图, $n_{1}, n_{2}, n_{3}, n_{4}\geq 4$,

$ \nu(G)=(n_{1}+1)(n_{2}+1)(n_{3}+1)(n_{4}+1), $

则有$G\cong HPK(n_{1}+1, n_{2}+1, n_{3}+1, n_{4}+1)$.

为了证明此定理, 先做一些预备知识.

假设

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

则$G$中两个顶点$x=(x_{1}, x_{2}, x_{3}, $ $x_{4})$, $y=(y_{1}, y_{2}, y_{3}, y_{4})$彼此不邻接, 当且仅当$x_{i}\neq y_{i}, i=1, 2, 3, 4$.令$G-N^{*}(u)=H\cong HPK(n_{1}, n_{2}, n_{3}, n_{4}), u\in G$.首先定义$H$中的顶点, 令

$ \begin{equation} \label{eq:1} V(H)=\{(x_{1}, x_{2}, x_{3}, x_{4})|1\leq x_{i}\leq n_{i}, i=1, 2, 3, 4\}, \end{equation} $

(2.1)

$H$中两个顶点$x=(x_{1}, x_{2}, x_{3}, $ $x_{4})$, $y=(y_{1}, $ $y_{2}, y_{3}, y_{4})$彼此不邻接, 当且仅当$x_{i}\neq y_{i}, $ $i=1, 2, 3, 4$.

由(2.1) 式知, 在$H$中已经命名的顶点和定义两个顶点邻接的条件为方便起见都称为命名原则.同样, 可以命名$G$中的顶点, 对于$x\in G$, 令$x=(x_{1}, x_{2}, x_{3}, x_{4})$, $0\leq x_{i}\leq n_{i}$.由此可知定理的证明过程实际上是一个合理的命名过程, 只要命名是合理的并遵循一定的命名原则即可.

下面根据$H$中的命名原则一步一步的命名$N^{*}(v)$中的点, 其中$H=G-N^{*}(v)$.令$v_{k}=(k, k, \cdots, k), $ $ k=1, 2, 3, 4$, $H_{k}=G-N^{*}(v_{k})\cong HPK(n_{1}, n_{2}, n_{3}, n_{4}), $ $k=1, 2, 3, 4$.由引理2.3知

$ \begin{eqnarray} N^{*}(v)&\;=&\; N^{*}_{H_{1}}(v)\cup(N^{*}_{H_{2}}(v)\cap N^{*}_{H_{2}}(v_{1}))\cup (N^{*}_{H_{3}}(v)\cap N^{*}_{H_{3}}(v_{1})\cap N^{*}_{H_{3}}(v_{2}))\nonumber\\ && \cup (N^{*}_{H_{4}}(v)\cap N^{*}_{H_{4}}(v_{1})\cap N^{*}_{H_{4}}(v_{2})\cap N^{*}_{H_{4}}(v_{3}))\nonumber \\ && \cup (N^{*}(v)\cap N^{*}(v_{1})\cap N^{*}(v_{2})\cap N^{*}(v_{3})\cap N^{*}(v_{4})). \end{eqnarray} $

(2.2)

由引理2.3, 2.4可知

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

最后根据(2.2) 式可知

$ N^{*}(v)\cap N^{*}(v_{1})\cap N^{*}(v_{2})\cap N^{*}(v_{3})\cap N^{*}(v_{4})=\phi. $

为了完成$G$中的顶点的命名, 我们需要一些命名规则, 于是有下面引理.

引理 2.5  令

$ \begin{eqnarray*}&& H=HPK(n_{1}, n_{2}, n_{3}, n_{4}), n_{1}, n_{2}, n_{3}, n_{4}\geq4, \\ && V(F)=\{(x_{1}, x_{2}, x_{3}, x_{4}) |1\leq x_{i}\leq n_{i}, i=1, 2, 3, 4\}, \end{eqnarray*} $

$x=(x_{1}, x_{2}, x_{3}, x_{4})$和$y=(y_{1}, y_{2}, y_{3}, y_{4})$是彼此不邻接的, 当且仅当$x_{i}\neq y_{i}, i=1, 2, 3, 4$.令$v=v_{1}=(1, 1, 1, 1)$, $F_{1}=H-N^{*}(v_{1})=\langle (x_{1}, x_{2}, x_{3}, x_{4})|2\leq x_{i}\leq n_{i}, i=1, 2, 3, 4 \rangle$.则有

C$_{1}$ $i_{1}, \cdots, i_{l}, \cdots, i_{4}$是$\{1, 2, 3, 4\}$的一个排列, 这里

$ 1\leq i_{1}<\cdots<i_{l}\leq 4, 1\leq i_{l+1}<\cdots<i_{4}\leq 4, 1\leq l\leq 3. $

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

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

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

C$_{5}$ $u_{k}=(u_{1}^{k}, \cdots, u_{r}^{k}), k=1, \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_{4}}^{k}=2$, 则有一个唯一的点$x^{*}\in N_{F}^{*}(v)$, 即

C$_{6}$ $x^{*}$与$u_{1}, \cdots, u_{l}$邻接.

C$_{7}$ $x^{*}$与$Y$的顶点彼此不邻接.

证  令$x^{*}=(x_{1}, x_{2}, x_{3}, x_{4})$, $x_{i_{k}}=a_{k}, k=1, \cdots, l, x_{i_{l+1}}=\cdots=x_{i_{4}}=1$.容易验证, $x^{*}$满足C$_{6}$和C$_{7}$.如果$t=(t_{1}, t_{2}, t_{3}, t_{4})\in N^{*}(v_{1})$满足C$_{6}$和C$_{7}$, 则$t$表示法是唯一的.因为$t$是不邻接$Y$中的点, 因此有$t_{i_{l+1}}=\cdots=t_{i_{4}}=1$, 剩下只需证明$t_{i_{k}}=a_{k}$, $t$是不邻接$Y$中的点, 所以$t_{i_{k}}$仅仅只能表示为$a_{k}$或者1, 特别$t_{i_{k}}\neq b_{k}$.又因为$t$不邻接$u_{k}$, 所以有$t_{i_{k}}=a_{k}, k=1, \cdots, l$.

为了测定$N^{*}(v_{1})$中的顶点, 根据引理2.5可知C$_{1}$, C$_{2}$, C$_{3}$是命名系统的关键条件.由于C$_{4}$中$b_{1}, \cdots, b_{l}$的选择不是唯一的, 因此导致$u_{1}, \cdots, u_{l}$也不是唯一的, 所以我们把C$_{1}$, C$_{2}$, C$_{3}$作为命名系统的条件.

引理 2.6  在引理2.5中C$_{1}$, C$_{2}$, C$_{3}$的命名原则唯一的确定了$ N(v_{1})$的点$x$, 反过来如果$N(v_{1})$中每一个点$x$都确定了, 则也确定了C$_{1}$, C$_{2}$, C$_{3}$的系统命名原则.

证  根据引理2.5很容易证明引理的前半部分, 下证后半部分.令

$ x=(x_{1}, x_{2}, x_{3}, x_{4})\in N(v_{1}), $

有一个特别的排列如下：

C$_{1}$ $i_{1}, \cdots, i_{l}, \cdots, i_{4}$, $1\leq i_{1}<\cdots<i_{l}\leq 4$, $1\leq i_{l+1}<\cdots<i_{4}\leq 4, 1\leq l\leq 3$, 这里$x_{i_{l+1}}=\cdots=x_{i_{4}}=1$, $x_{i_{1}}, \cdots, x_{i_{l}}\neq1$.所以有下列排列:

C$_{2}$ $a_{1}, \cdots, a_{l}$是一个排列, $a_{k}=x_{i_{k}}$, $2\leq a_{k}\leq n_{i_{k}}, k=1, \cdots, l$, 以及

C$_{3}$ $Y=\{(y_{1}, y_{2}, y_{3}, y_{4})\in F_{1}|y_{i_{k}}\neq a_{k}, k=1, \cdots, l\}$.证毕

根据引理2.5, 2.6可知如果在$N_{H}(v)$有未命名的点$x$, 这里$H=HPK(n_{1}, n_{2}, n_{3}, n_{4})$, $n_{1}, n_{2}, n_{3}, n_{4}\geq 4$, 则可以找一些属于$H$中的点$v$, 然后再来命名.根据在$H-N^{*}(v)$中的点命名规则, 新的命名规则可以与引理2.5的命名规则类似.

根据合理的命名原则, $N^{*}(v)$中的点也可以使用引理2.5的命名规则, 所以先命名$v=(0, 0, 0, 0)$, 再命名$N(v)$其它的点.于是有

M$_{1}$首先命名$N_{H_{1}}(v)$的点.因为

$ \begin{eqnarray*}&& H=G-N^{*}(v_{1}), v_{1}=(1, 1, 1, 1), \\ && V(H_{1})=\{(x_{1}, x_{2}, x_{3}, x_{4})|0\leq x_{i}\leq n_{i}, x_{i}\neq1\}.\end{eqnarray*} $

命名$N_{H_{1}}(v)$中的点可以使用$V(H_{1})-N^{*}(v)=V(H)-N^{*}(v_{1})=G-N^{*}(v)-N^{*}(v_{1})$的命名, 因此可以在$H=G-N^{*}(v)$中.根据引理2.5, 2.6的命名原则, 只需要用1代替0, 然后可以彻底的命名$N_{H_{1}}(v)$中的点.

M$_{2}$ 下面给$N_{H_{2}}(v)\cap N_{H_{2}}(v_{1})$中的点命名, 因为

$ \begin{eqnarray*}&& H_{2}=G-N^{*}(v_{2})\cong HPK(n_{1}, n_{2}, n_{3}, n_{4}), v_{2}=(2, 2, 2, 2), \\ && H-N^{*}(v_{k})=G-N^{*}(v)-N^{*}(v_{k})=H_{k}-N^{*}(v)=F_{k}, \\ && V(H_{2})=\{(x_{1}, x_{2}, x_{3}, x_{4})|0\leq x_{i}\leq n_{i}, x_{i}\neq2, i=1, 2, 3, 4\}. \end{eqnarray*} $

为了命名$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}$中重申这些顶点的命名条件, 即

C$_{1}$ $ i_{1}, \cdots, i_{l}, \cdots, i_{4}$是一个排列.

C$_{2}$ $a_{1}, \cdots, a_{l}$是一个序列, $1\leq a_{k}\leq n_{i_{k}}, a_{k}\neq2, k=1, \cdots, l, 1\in\{a_{1}, \cdots, a_{l}\}$.

C$_{3}$ $Y=\{(y_{1}, y_{2}, y_{3}, y_{4})\in F_{2}|y_{i_{k}}\neq a_{k}, k=1, \cdots, l\}$.

C$_{2}$增加一个条件$1\in\{a_{1}, \cdots, a_{l}\}$, 主要是可以保证顶点$x^{*}$根据$C_{1}, C_{2}, C_{3}$是属于$N_{H_{2}}^{*}(v)\cap N_{H_{2}}^{*}(v_{1})$.如果忽略此条件, 根据系统的命名的唯一性原则, 只能唯一确定$N_{H_{2}}^{*}(v)$中的一个点$x^{*}$.增加此条件后, 我们可以将$N_{H_{1}}^{*}(v)\cap N_{H_{2}}^{*}(v)$中的点命名两个名字.为了保证合理的命名, 需要标明$ (N_{H_{1}}^{*}(v)\cap N_{H_{2}}^{*}(v))$一个点$x^{*}$的两个名字分别是$H_{1}$和$H_{2}$中命名一致的点.

由于$x^{*}\in (N_{H_{1}}^{*}(v)\cap N_{H_{2}}^{*}(v))$, $x^{*}$已经在$H_{1}$中命名为$(x_{1}, x_{2}, x_{3}, x_{4})$.因为$x^{*}$是不邻接$v_{2}=(2, 2, 2, 2)\in H_{1}$, 所以在$H_{1}$中命名条件C$_{1}$和C$_{2}$可以是这样

C$_{1}$ $i_{1}, \cdots, i_{l}, \cdots, i_{4}$是一个排列, 这里$x_{i_{1}}, \cdots, x_{i_{l}}\neq0, 1, 2$, $x_{i_{l+1}}=\cdots=x_{i_{l}}=0$.

C $_{2}$ $a_{1}, \cdots, a_{l}$是一个序列, $ a_{k}= x_{i_{k}}\neq0, 1, 2, k=1, \cdots, l$.

这些命名条件在$H_{2}$中的点也类似, 令$H_{2}$中的点$x^{**}=(x_{1}^{'}x_{2}^{'}, x_{3}^{'}, x_{4}^{'})$, 这里$x_{i_{k}}^{'}=a_{k}, k=1, 2, \cdots, l$以及$x_{i_{l+1}}^{'}=\cdots=x_{i_{l}}^{'}=0$, 由于$a_{k}\neq0, 1, 2$.又因为$v_{1}=(1, 1, 1, 1)\in H_{2}$, 因此$x^{**}$是不邻接$v_{1}$, $x^{**}\in (N_{H_{1}}^{*}(v)\cap N_{H_{2}}^{*}(v))$, 所以$x^{**}=x^{*}$, 由此可知$x^{*}$在$ H_{2}$中的命名与在$ H_{1}$中命名一样.

类似, 归纳定义以下名称:

M$_{3}$ $N_{H_{3}}(v)\cap N_{H_{3}}(v_{1})\cap N_{H_{3}}(v_{2})$.

M$_{4}$ $N_{H_{4}}(v)\cap N_{H_{4}}(v_{1})\cap N_{H_{4}}(v_{2})\cap N_{H_{4}}(v_{3})$.

最后完整的命名$G$中的点, 即$V(G)=\{(x_{1}, x_{2}, x_{3}, x_{4})|0\leq x_{i}\leq n_{i}\}$.根据$G$中的点的命名, 令$x=(x_{1}, x_{2}, x_{3}, x_{4})$和$y=(y_{1}, y_{2}, y_{3}, y_{4})$彼此不邻接, 当且仅当$x_{i}\neq y_{i}, i=1, 2, 3, 4$.

引理 2.7  设$G$是$HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图, $n_{1}, n_{2}, n_{3}, n_{4}\geq 4$, 则对$G$中任意两个顶点$u, v$, 则存在一个点$w\in G$, 使得$u, v\in( V(G)-N^{*}(w))$.

证  根据定义2.3可以证明.

定理2.2的证明  对于$G$中任意两个点$x$和$y$, 根据引理2.7, 存在一个点$w$既不与$x$邻接也不与$y$邻接.假设$w\in H_{k}$, 对于每一个$k, $如果既有$x\in H_{k}$又有$y \in H_{k}$, 则可以通过$H_{k}$中的命名原则.特别让$H^{*}=G-N^{*}(w)\cong HPK(n_{1}, n_{2}, n_{3}, n_{4})$, 则有$x, y\in H^{*}$.根据$H_{k}$中的命名原则, 可以重命名$G$中的所有点.因此, 根据命名的唯一性, $G$中的所有点重命名与原来类似, 根据这一事实$x, y\in H^{*}=G-N^{*}(w)$, 由引理2.5, 2.6知, $H^{*}$的顶点命名是合理的, 所以$x=(x_{1}, x_{2}, x_{3}, x_{4})$与$y=(y_{1}, y_{2}, y_{3}, y_{4})$是彼此不邻接的, 因此证明了$G\cong HPK(n_{1}+1, n_{2}+1, n_{3}+1, n_{4}+1)$.

引理 3.1  设$G=(V, E)$, $\{v_{0}, v_{1}, v_{2}, v_{3}, v_{4}\}\in G\subset V(G)$是$G$的$5$ -独立集, 则

$ \begin{eqnarray*}&& N^{*}(v_{1})\cap N^{*}(v_{2})\cap N^{*}(v_{3})\cap N^{*}(v_{4})= (N^{*}_{F}(v_{1})\cap N^{*}_{F}(v_{2})\cap N^{*}_{F}(v_{3})\cap N^{*}_{F}(v_{4}))\\ && \cup(N^{*}(v_{1})\cap N^{*}(v_{2})\cap N^{*}(v_{3}) \cap N^{*}(v_{4})\cap N^{*}(v_{0})), \end{eqnarray*} $

这里$F=G-N^{*}(v_{0})$.

证  由集合的运算性质知显然成立.

引理 3.2  令$G=(V, E)$, $u_{1}, u_{2}, \cdots, u_{k}\in G$和$\{v_{0}, v_{1}, v_{2}, v_{3}, v_{4}\}\subset V(G)$是$G$的$5$ -独立集, 每一个$v_{i}$不邻接$u_{j}$.令$F_{i}=G-N^{*}(v_{i}), i=1, 2, 3, 4 $, 则有

$ 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(N^{*}_{F_{3}}(u_{1})\\\;\;\;\;\cap N^{*}_{F_{3}}(u_{2})\cap\cdots\\ \cap N^{*}_{F_{3}}(u_{k})\cap N^{*}_{F_{3}}(v_{1})\cap N^{*}_{F_{3}}(v_{2}))\cup (N^{*}_{F_{4}}(u_{1})\cap N^{*}_{F_{4}}(u_{2})\cap\cdots\cap N^{*}_{F_{4}}(u_{k})\\\;\;\;\;\cap N^{*}_{F_{4}}(v_{1})\cap N^{*}_{F_{4}}(v_{2})\\ \cap N^{*}_{F_{4}}(v_{3}))\cup (N^{*}(u_{1})\cap N^{*}(u_{2})\cap\cdots \cap N^{*}(u_{k})\cap N^{*}(v_{1})\cap N^{*}(v_{2}) \\\;\;\;\;\cap N^{*}(v_{3})\cap N^{*}(v_{4})). $

证  由集合的运算性质知结论显然成立.

引理 3.3  假设$G$是$HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图,

$ H=HPK(n_{1}+1, n_{2}+1, n_{3}+1, n_{4}+1), n_{1}, n_{2}, n_{3}, n_{4}\geq 4. $

令$\{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 5$, 由引理2.2知

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

所以不等式显然成立.假设$1\leq k\leq 4$, 令$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}, n_{3}, n_{4})$, 有$\{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$ -独立集合, 所以有

$ \begin{eqnarray*}&& |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)|. \end{eqnarray*} $

因为$G_{1}\cong H_{1}\cong HPK(n_{1}, n_{2}, n_{3}, n_{4})$, 根据引理2.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=4, 3, 2, 1$, 不等式取等号成立, 当$k\geq 5$, 不等式显然成立.证毕

引理 3.4  设$G$是2-$HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图,

$ H=HPK(n_{1}+2, n_{2}+2, n_{3}+2, n_{4}+2), n_{1}, n_{2}, n_{3}, n_{4}\geq 4, $

$\{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})|. $

证  由引理2.2知, 当$k\geq 5$, 不等式显然成立.当$1\leq k\leq 4$, 从引理3.3讨论的可知, 令$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}, n_{3}, n_{4})$ -残差图, 又由于

$ H_{1}=HPK(n_{1}+1, n_{2}+1, n_{3}+1, n_{4}+1), $

根据引理3.3证明过程可知, 当$k=4, 3, 2, 1$时, 不等式取等号成立.证毕

引理 3.5  设$G$是$m$-$HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图,

$ H=HPK(n_{1}+m, n_{2}+m, n_{3}+m, n_{4}+m), n_{1}, n_{2}, n_{3}, n_{4}\geq 4, $

$\{v_{1}, v_{2}, v_{3}, v_{4}\}\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, $由引理3.3, 3.4, 不等式显然成立.假设当$m-1$时, 定理成立.对于$ m$, 根据引理2.3, 当$k\geq 5$时, 不等式显然成立.同样根据引理3.3, 3.4的讨论过程知, 当$k=4, 3, 2, 1$时, 不等式等号成立, 从而证明此定理.

定理 3.1  设$G$是$m$-$HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图, $n_{1}, n_{2}, n_{3}, $ $n_{4}\geq 4$, 则有

$ \nu(G)\geq (n_{1}+m)(n_{2}+m)(n_{3}+m)(n_{4}+m). $

证  当$m=1$时, 由定理2.1知, 结论显然成立.假设当$m-1$时, 结论成立.当等于$m$时, 令$G$是$m-HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图, $H=HPK(n_{1}+m, n_{2}+m, n_{3}+m, n_{4}+m)$.从引理3.4可知

$ |N^{*}_{G}(v)|\geq |N^{*}_{H}(u)|, $

对任意的$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}, n_{3}, n_{4})$ -残差图, 即为

$ H_{1}=HPK(n_{1}+m-1, n_{2}+m-1, n_{3}+m-1, n_{4}+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)(n_{3}+m)n_{4}+m). $

定理 3.2  设$G$是$m$-$HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图, $n_{1}, n_{2}, n_{3}, n_{4}\geq 4$,

$ \nu(G)= (n_{1}+m)(n_{2}+m)(n_{3}+m)(n_{4}+m), $

则有

$ G\cong HPK(n_{1}+m, n_{2}+m, n_{3}+m, n_{4}+m). $

证  设$G$是一个$m$-$HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图,

$ H=HPK(n_{1}+m, n_{2}+m, n_{3}+m, n_{4}+m), n_{1}, n_{2}, n_{3}, n_{4}\geq 4, $

$\nu(G)=\nu(H)$.当$m=1$, 由定理3.1知

$ G\cong HPK(n_{1}+1, n_{2}+1, n_{3}+1, n_{4}+1), $

结论成立.假设当$m-1$时, 结论成立.当等于$m$时, 对于$v\in G$和$u\in H$, 则有$G_{1}=G-N^{*}(v)$是$(m-1)$-$HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图, 由归纳假设有

$ H_{1}=H-N^{*}(u)=HPK(n_{1}+m-1, n_{2}+m-1, n_{3}+m-1, n_{4}+m-1). $

根据引理3.5和定理3.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)(n_{3}+m-1)(n_{4}+m-1). $

$G_{1}$是最小阶的$(m-1)-HPK(n_{1}, n_{2}, n_{3}, n_{4})$ -残差图.由归纳假设有

$ G_{1}\cong HPK(n_{1}+m-1, n_{2}+m-1, n_{3}+m-1, n_{4}+m-1). $

由于$G$中点$v$选择的任意性, 再根据定义2.2, 2.3知, $G$是最小阶的$HPK(n_{1}+m-1, n_{2}+m-1, n_{3}+m-1, n_{4}+m-1)$ -残差图, 又有$n_{i}^{'}=n_{i}+m-1\geq n_{i}\geq 4, $ $i=1, 2, 3, 4$.所以由定理2.2知$G\cong HPK(n_{1}+m, n_{2}+m, n_{3}+m, n_{4}+m)$.