有遗失边的k元n立方体在MM*模型下的局部诊断度

Local Diagnosability of k-Ary n-Cubes with Missing Edges under the MM* Model

摘要: 一个多重处理器系统的诊断度是一个非常重要的研究课题，它是度量多重处理器系统故障诊断的重要参数。作为重要的互连网络拓扑结构，k元n立方体具有许多良好的性质。在本文中，我们研究了k元n立方体Q_n^k(n≥3,k≥6)在MM*模型下的局部诊断度，证明了Q_n^k(n≥3,k≥6)即使存在2n-2条遗失边仍具有强局部诊断性，并且证明了2n-2是最优值。

Abstract: Diagnosability is an important research subject and parameter in measuring the fault diagnosis of multiprocessor systems. As a celebrated topology structure of interconnection networks, a k-ary n-cube Q_n^k has numerous great properties. In this paper, we study the diagnosability of k-ary n-cubes Q_n^k and demonstrate that Q_n^k(n≥3,k≥6) possesses the strong property even if there exist 2n-2 missing edges in it under the MM* model and the result is optimal with respect to the number of missing edges.

1. 引言

大部分多重处理器系统都以互连网络作为基本的拓扑结构并且通常用图来表示一个互连网络，其中顶点代表处理器，边代表处理器之间的通信链路。我们用图和网络互换。对于多重处理器系统来说，其网络拓扑性质的研究是非常重要的。诊断度是度量多重处理器系统故障诊断能力的重要参数，它是互连网络中热门的研究课题之一。此外，在系统中，一些处理器可能是故障的。所以，为了保证计算机系统的可靠性，系统中的故障处理器应该被诊断出来，处理故障系统的第一步是故障识别，在多重处理器系统中存在的故障处理器在此步中一一被识别出来，这一识别过程被称为系统的诊断。在之前的研究中，研究者已经提出了许多系统诊断模型，其中被广泛使用的是比较模型(MM模型)。MM模型是由Malek和Maeng [1] 首次提出的。后来，Sengupta和Dahbura [2] 提出了MM*模型，它是MM模型的一个特例。Dahbura和Masson [3] 提出了一个时间复杂度为 $O\left(n^{2.5}\right)$ 的算法。在故障处理器的数量不超过t的情况下，如果所有故障的处理器能够被识别出来并且不被替换，我们就称这个系统是t-可诊断的。一个系统G的诊断度 $t\left(G\right)$ 是使得G是t-可诊断的t的最大值 [4] [5] [6] [7]。

在之前的研究中，人们一直考虑的是一个多重处理器系统的全局诊断度。在文献 [8] 中，Hsu和Tan首次提出了一种测量多重处理器系统G的局部诊断度的概念。这种新的概念研究的是每个处理器的局部性质而不是全局性质。如果我们只考虑全局故障或无故障状态，我们就会失去系统的一些细节。在文献 [9] 中，Chiang和Tan提出了一种有用的确定系统诊断度的新方法，即延展星结构法。该方法可以保证节点的诊断性，并给出了比较诊断模型(MM模型)下局部可诊断性的充分条件，他们发现在局部诊断性和传统的诊断性之间存在很强的关系。如果系统G中每个点的局部诊断性等于它的度，那么系统G具有强局部诊断性。根据这个概念，强局部诊断性被广泛研究。在文献 [10] 中，Chiang等人证明了 $n\left(n\ge 4\right)$ 维星图的诊断性是 $n-1$，且即使它存在 $n-3$ 条遗失边，仍保持强局部诊断性。后来，Cheng等又研究了置换树生成的Cayley图 [11] 和 $\left(n,k\right)$ 星图和2树生成的Cayley图 [12]。在2018年，Wang和Ma [13] 证明了交错群图 $A{G}_n$ 在MM*模型下即使存在 $2n-7$ 条遗失边，仍保持强局部诊断性。2020年，Wang和Ma [14] 证明了排列图 $A_{n,k}$ 在MM*模型下即使存在 $\left(k-1\right)\left(n-k\right)-1$ 条遗失边，仍保持强局部诊断性，且证明了 $\left(k-1\right)\left(n-k\right)-1$ 是最优值。2020年，Zhou [15] 等人证明了扩展k元n立方体 $X{Q}_n^k$ 在比较模型下即使存在 $4n-5$ 条遗失边，仍保持强局部诊断性。2020年，Feng [16] 等人证明了轮图 $C{W}_n$ 在MM*模型下即使存在 $2n-4$ 条遗失边，仍保持强局部诊断性，且证明了 $2n-4$ 是最优值。2021年，Fan [17] 等人证明了 $Q_n$ 在MM*模型下即使存在 $n-2$ 条遗失边仍具有强局部诊断性，并且证明了 $n-2$ 是最优值。同时，他们证明了 $F{Q}_n$ 在MM*模型下即使存在 $n-1$ 条遗失边仍具有强局部诊断性，并且证明了 $n-1$ 是最优值。

k元n立方体 $Q_n^k$ 有许多良好的性质。比如点传递性 [18]，边传递性 [19]，小直径 [20] [21] 等。在这篇文章中，我们证明了 $Q_n^k$ 的诊断度是2n，且在MM*模型下即使存在 $2n-2$ 条遗失边，仍保持强局部诊断性并且是最优的。

2. 基本概念

多重处理器系统被表示为一个无向的简单图 $G=\left(V,E\right)$，其中 $V=V\left(G\right)$， $E=E\left(G\right)$，分别表示图G的顶点集和边集，且顶点集 $V\left(G\right)$ 代表处理器，边集 $E\left(G\right)$ 代表处理器之间的通信链路。对于任意的非空顶点子集 $V^{\prime }\subset V$，则以两端点均在 $V^{\prime }$ 中的边的全体为边集所组成的子图，称为 $V^{\prime }$ 在G中的导出子图，记作 $G\left[V^{\prime }\right]$。 $d_G\left(v\right)$ 是指G中与v关联的边的数目， $\delta (G)$ 表示G中顶点的最小度。对于G中任意一个顶点v，都有 $d_G\left(v\right)=k$，则称图G是k-正则的。对于任意 $v\in V$， $N_G\left(v\right)$ 表示G中与v相邻的所有顶点组成的集合。对于 $u\in N_G\left(v\right)$，u称为v的一个邻点。对于邻集、度等这些概念，在没有歧义产生时，我们通常省略图的下标。G的一条途径是指一个有限非空序列 $P=v_0{e}_1{v}_1{e}_2{v}_2\cdots e_n{v}_n$，它的项交替地为顶点和边，使得对 $1\le i\le n$， $e_i$ 的端点是 $v_{i-1}$ 和 $v_i$，称P是从 $v_0$ 到 $v_n$ 的一条途径。 $v_0$ 和 $v_n$ 分别称为P的起点和终点，整数n称为P的长。若途径P的顶点 $v_0,v_1,\cdots ,v_n$ 互不相同，则P称为路。我们用 $P=\langle v_0,v_1,\cdots ,v_n\rangle$ 表示一条长为n的起点是 $v_0$，终点是 $v_n$ 的路。如果把G的点集任意划分为两个非空子集X和Y，总存在一条边满足其中一个端点在X中，另一个端点在Y中，那么G是连通的。一个图G的连通度 $\kappa \left(G\right)$ 和边连通度 $\lambda \left(G\right)$ 分别是把图G变成一个不连通图或仅一个点所需移除的点和边的最小数量。一个二部图是一个点集能分解成两个子集X和Y的图，使得每条边都有一个端点在X中，另一个端点在Y中，这样的划分 $\left(X,Y\right)$ 被称为图的一个二分类。一个图 $G_1$ 与另一个图 $G_2$ 同构(记为 $G_1\cong G_2$ )当且仅当存在一个双射 $\phi :V\left(G_1\right)\to V\left(G_2\right)$ 使得对于任意两个顶点 $u,v\in V\left(G_1\right)$， $uv\in E\left(G_1\right)$， $\phi \left(u\right)\phi \left(v\right)\in E\left(G_2\right)$。文中其他未定义而直接使用的符号和术语参见文献 [22]。

3. MM*模型

在MM模型中，一个处理器发送同样的任务给一对不同的邻点，然后比较它们的反应结果。一个系统 $G=\left(V\left(G\right),E\left(G\right)\right)$ 的比较方案被建模为一个多重图，用 $M=\left(V\left(G\right),L\right)$ 表示，其中L是被标记的边集。一条被标记的边 ${\left(u,v\right)}_w\in L$ 代表用一个顶点w去比较两个相邻顶点u和v，这意味着 $uw,vw\in E\left(G\right)$。如果节点w是非故障的(故障的)，那么测试结果是可靠的(不可靠的)。如果 $u,v\in F$ 且 $w\in V\left(G\right)\backslash F$，则 ${\left(u,v\right)}_w\to 1$。如果 $u\in F$ 且 $v,w\in V\left(G\right)\backslash F$，则 ${\left(u,v\right)}_w\to 1$。如果 $v\in F$ 且 $u,w\in V\left(G\right)\backslash F$，则 ${\left(u,v\right)}_w\to 1$。如果 $u,v,w\in V\left(G\right)\backslash F$，则 ${\left(u,v\right)}_w\to 0$。 $M=\left(V\left(G\right),L\right)$ 中所有比较结果的集合称为诊断的症候，用 $\sigma$ 表示。如果比较 ${\left(u,v\right)}_w$ 的结果不一致，则 $\sigma \left({\left(u,v\right)}_w\right)=1$ ；否则， $\sigma \left({\left(u,v\right)}_w\right)=0$。因此，一个症候是从L到 $\left\{0,1\right\}$ 的一个函数。MM*中每个节点必须测试其任意一对相邻节点。即如果 $uw,vw\in E\left(G\right)$，则 ${\left(u,v\right)}_w\in L$。在系统中，所有故障处理器的集合叫做一个故障集，它可以是 $V\left(G\right)$ 的任意一个子集。在MM*模型下，对于一个给定的症候 $\sigma$，如果对任意的 ${\left(u,v\right)}_w\in L$ 满足 $w\in V\backslash F$， $\sigma \left({\left(u,v\right)}_w\right)=1$ 当且仅当 $u,v\in F$ 或 $u\in F$ 或 $v\in F$，则我们称故障子集 $F\subseteq V\left(G\right)$ 和 $\sigma$ 是一致的。我们用 $\sigma \left(F\right)$ 表示和F一致的所有症候的集合。设 $F_1$ 和 $F_2$ 是 $V\left(G\right)$ 中两个不同的子集。如果 $\sigma \left(F_1\right)\cap \sigma \left(F_2\right)\ne \varnothing$，则 $\left(F_1,F_2\right)$ 是不可区分对；否则， $\left(F_1,F_2\right)$ 是可区分对。

定义3.1 [15] 一个系统 $G=\left(V,E\right)$ 是t-可诊断的，当且仅当V中每一对不同的故障子集 $F_1$ 和 $F_2$，其中 $\left|F_1\right|\le t$， $\left|F_2\right|\le t$， $\left(F_1,F_2\right)$ 是可区分对。

设 $F_1$， $F_2$ 是 $G=\left(V,E\right)$ 中两个不同子集，对称差 $F_1△F_2=\left(F_1\backslash F_2\right)\cup \left(F_2\backslash F_1\right)$。

定理3.1 [2] [3] 一个系统 $G=\left(V,E\right)$ 在MM*模型下是t-可诊断的，当且仅当对于V的每一对不同的故障集 $F_1$ 和 $F_2$，其中 $\left|F_1\right|\le t$， $\left|F_2\right|\le t$，满足下列条件之一(见图1)：

1) 存在 $u,w\in V\backslash \left(F_1\cup F_2\right)$ 和 $v\in F_1△F_2$ 满足 $uw\in E$， $vw\in E$。

2) 存在 $u,v\in F_1\backslash F_2$ 和 $w\in V\backslash \left(F_1\cup F_2\right)$ 满足 $uw\in E$， $vw\in E$。

3) 存在 $u,v\in F_2\backslash F_1$ 和 $w\in V\backslash \left(F_1\cup F_2\right)$ 满足 $uw\in E$， $vw\in E$。

Figure 1. Illustration of a distinguishable pair under the MM* model

图1. 在MM*模型下可区分

4. 局部诊断度

引理4.1 [10] 系统 $G=\left(V,E\right)$ 在x点处是局部t-可诊断的，如果给定一个测试症候 ${\sigma }_F$，它是由系统在一组包含x的故障顶点集F的情况下产生的， $\left|F\right|\le t$，那么故障顶点集 $F^{\prime }$ 的每一个集合与 ${\sigma }_F$ 一致，且 $\left|F^{\prime }\right|\le t$ 必须包含顶点x。

引理4.2 [9] 系统 $G=\left(V,E\right)$ 中，如果 $x\in F_1△F_2$ 且对于V的每一对不同的故障子集 $F_1$ 和 $F_2$ 是可区分的，其中 $\left|F_1\right|\le t$， $\left|F_2\right|\le t$，则点x是局部t-可诊断的。

引理4.1和引理4.2是等价的。

引理4.3 [10] 一个系统 $G=\left(V,E\right)$ 是t-可诊断的当且仅当G中每个点都是局部t-可诊断的。

引理4.4 [10] 一个系统 $G=\left(V,E\right)$ 中，G中x点是局部t-可诊断的t的最大值被定义为点x的局部诊断度 $t_l\left(x\right)$，即 $t_l\left(x\right)=\max \left\{t:G在x点是局部t\text{-}可诊断的\right\}$。

引理4.5 [10] 一个系统 $G=\left(V,E\right)$ 的诊断度 $t\left(G\right)$ 等于G中每个点的局部诊断度的最小值，即 $t\left(G\right)=\min \left\{t_l\left(x\right):对于所有的x\in V\left(G\right)\right\}$。

定义4.1 [10] 设x是一个图 $G=\left(V,E\right)$ 中的一个点。若 $d_G\left(x\right)\ge n$，我们定义一个延展星图 $ES\left(x;n\right)$，其中 $d_{ES\left(x;n\right)}\left(x\right)=n$，点集 $V\left(ES\left(x;n\right)\right)=\left\{x\right\}\cup \left\{v_{ij}:i=1,2,\cdots ,n;j=1,2,3,4\right\}$，边集 $E\left(ES\left(x;n\right)\right)=\left\{\left(x,v_{i1}\right),\left(v_{i1},v_{i2}\right),\left(v_{i2},v_{i3}\right),\left(v_{i3},v_{i4}\right):i=1,2,\cdots ,n\right\}$。

注意到x称为 $ES\left(x;n\right)$ 的根。

引理4.6 [10] 设x是系统 $G=\left(V,E\right)$ 中的一个点且 $d_G\left(x\right)=n$。如果点x在G中存在一个延展星图 $ES\left(x;n\right)$，则x的局部诊断度是n。

引理4.7 [23] 设G是一个系统的图表示，那么在MM*模型下，诊断度 $t\left(G\right)\le \delta \left(G\right)$。

引理4.8 [10] 设x是图 $G=\left(V,E\right)$ 中的一个点。如果x的局部诊断度等于它在G中的度，即 $t_l\left(x\right)=d_G\left(x\right)$，则这个点x有强局部诊断性。

引理4.9 [10] 设 $G=\left(V,E\right)$ 是一个图。如果G中每个点的局部诊断度都等于它在G中的度，即对于所有的 $x\in V\left(G\right)$ 都有 $t_l\left(x\right)=d_G\left(x\right)$，则G有强局部诊断性。

5. k元n立方体 $Q_n^k$

定义5.1 [24] k元n立方体 $Q_n^k\left(n\ge 1,k\ge 3\right)$ 是一个有 $k^n$ 个顶点和 $n{k}^n$ 条边的2n正则图。k元n立方体 $Q_n^k$ 的顶点u用长为n的二进制字符串表示，如 $u=u_0{u}_1\cdots u_{n-1}$，其中 $0\le u_i\le k-1$， $i=0,1,\cdots ,n-1$。两个顶点 $u=u_0{u}_1\cdots u_{n-1}$ 和 $v=v_0{v}_1\cdots v_{n-1}$ 相邻当且仅当存在一个整数 $j\in \left\{0,1,\cdots ,n-1\right\}$ 使得 $u_j=v_j\pm 1\left(\mathrm{mod}k\right)$，同时 $u_l=v_l$ 对于 $l\in \left\{0,1,\cdots ,n-1\right\}\backslash \left\{j\right\}$。为了陈述清晰，我们在后文中省略了类似“ $\left(\mathrm{mod}k\right)$ ”的表达形式。

我们将 $Q_n^k$ 划分为k个互不相交的子图 $Q_n^k\left[0\right],Q_n^k\left[1\right],\cdots ,Q_n^k\left[k-1\right]$ (在不产生歧义的前提下可以缩写为 $Q\left[0\right],Q\left[1\right],\cdots ,Q\left[k-1\right]$ )，各子图内每个顶点 $u=u_0{u}_1\cdots u_{n-1}\in V\left(Q_n^k\right)$ 在最后一个位置 $u_{n-1}$ 上有一个固定的整数i，其中 $i\in \left\{0,1,\cdots ,k-1\right\}$。显然， $Q\left[i\right]$ 同构于 $Q_{n-1}^k$，对于 $0\le i\le k-1$。6元1立方体，5元2立方体如图2所示。设 $u\in V\left(Q\left[i\right]\right)$，那么 $N\left(u\right)\backslash V\left(Q\left[i\right]\right)$ 称为u的外邻点集。连接来自不同子图 $Q\left[i\right]$ 和 $Q\left[j\right]$ 的顶点的边称为外部边，而将连接来自相同子图 $Q\left[i\right]$ 的顶点的边称为内部边。

Figure 2. (a) $Q_1^6$ ; (b) $Q_2^5$

图2. (a) 6元1立方体；(b) 5元2立方体

引理5.1 [18] [19] k元n立方体 $Q_n^k\left(k\ge 3\right)$ 是点传递和边传递的。

引理5.2 [18] k元n立方体 $Q_n^k$ 是二部图当且仅当k为偶数。

引理5.3 [18] k元n立方体 $Q_n^k\left(n\ge 2,k\ge 3\right)$ 有下列性质：

(1) $\kappa \left(Q_n^k\right)=\lambda \left(Q_n^k\right)=2n$。

(2) $Q\left[i\right]$ 中每个点与 $2n-2$ 条内部边关联，与2条外部边关联。

(3) $Q\left[i\right]$ 中每个点的两个外邻点在不同的子图中。

6. k元n立方体 $Q_n^k$ 的诊断度

引理6.1 对于k元n立方体 $Q_n^k\left(n\ge 3,k\ge 6\right)$ 中任意一点x，在x点处存在一个延展星图 $ES\left(x;2n\right)$。

证明 我们可以在x点处找到一个延展星图 $ES\left(x;2n\right)$ 作为k元n立方体 $Q_n^k$ 的子图。由引理5.1， $Q_n^k$ 是点传递的。不失一般性，设 $x=000\cdots 00=\left(0\right)$ 是延展星图 $ES\left(x;2n\right)$ 的根。当 $n=3$， $k\ge 6$ 时，我们可以在x点处找到一个延展星图 $ES\left(x;6\right)$ (见图3)。显然， $ES\left(x;6\right)$ 中的各点均不相同。

假设这个结论对于 $Q_{n-1}^k\left(n\ge 4,k\ge 6\right)$ 成立，即在 $Q_{n-1}^k$ 中存在一个延展星图 $ES\left(x;2n-2\right)$。现在我们证明这个结论对于 $Q_n^k$ 也成立，即在 $Q_n^k\left(n\ge 4,k\ge 6\right)$ 中存在一个延展星图 $ES\left(x;2n\right)$。我们根据最右边的位置将 $Q_n^k$ 划分为 $Q\left[0\right],Q\left[1\right],\cdots ,Q\left[k-1\right]$，那么 $Q\left[i\right]\left(0\le i\le k-1\right)$ 同构于 $Q_{n-1}^k$。由归纳假设，在 $Q\left[0\right]$ 中存在一个延展星图 $ES\left(x;2n-2\right)$。由引理5.3，点 $x=000\cdots 00=\left(0\right)\in V\left(Q\left[0\right]\right)$，它有两个外部邻点在不同的 $Q\left[j\right]$ 中，分别为： $000\cdots 01\in V\left(Q\left[1\right]\right)$ 和 $000\cdots 0\left(k-1\right)\in V\left(Q\left[k-1\right]\right)$。记 $P_1=\langle 000\cdots 01,100\cdots 01,200\cdots 01,210\cdots 01\rangle$ 是 $Q\left[1\right]$ 中的一条3长路， $P_2=\langle 000\cdots 0\left(k-1\right),100\cdots 0\left(k-1\right),200\cdots 0\left(k-1\right),300\cdots 0\left(k-1\right)\rangle$ 是 $Q\left[k-1\right]$ 中的一条3长路。我们将 $P_1$ 和 $P_2$ 都连接到x点，并且将它们与 $ES\left(x;2n-2\right)$ 相结合。因此，我们可以在 $Q_n^k$ 中x点处得到一个延展星图 $ES\left(x;2n\right)$，即在 $Q_n^k$ 中x点处存在一个延展星图 $ES\left(x;2n\right)$。

Figure 3. The first $ES\left(x;6\right)$ in $Q_3^k$

图3. $Q_3^k$ 的第一个延展星图 $ES\left(x;6\right)$

定理6.1 设 $Q_n^k$ 是一个k元n立方体且 $n\ge 3$， $k\ge 6$，则 $Q_n^k$ 的诊断度是2n，即 $t\left(Q_n^k\right)=2n$ 且 $Q_n^k$ 有强局部诊断性。

证明 通过引理4.6和引理6.1， $Q_n^k$ 中每个点x的局部诊断度是2n。由引理4.3， $Q_n^k$ 是2n-可诊断的。由 $Q_n^k$ 的定义可知， $\delta \left(Q_n^k\right)=2n$。由引理4.3和引理4.7， $t\left(Q_n^k\right)=2n$，即 $Q_n^k$ 的诊断度是2n。因为 $Q_n^k$ 中每个点x的度是2n， $Q_n^k$ 中每个点的局部诊断度等于它的度。由引理4.8， $Q_n^k$ 中每个点x有强局部诊断性。由引理4.9， $Q_n^k$ 有强局部诊断性。

引理6.2设 $F_e$ 是 $Q_n^k\left(n\ge 3,k\ge 6\right)$ 中任意的遗失边集， $\left|F_e\right|\le 2n-2$。 $Q_n^k-F_e$ 中存在一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$，其中 $x\in V\left(Q_n^k\right)$。

证明 由引理5.1， $Q_n^k$ 是一个点传递图，不失一般性，设 $x=00\cdots 00=\left(0\right)$ 是延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$ 的根。我们通过对n进行归纳来证明这个引理。当 $n=3$ 时，我们可以找到五个延展星图 $ES\left(x;6\right)$，它们的边除了与x关联的边之外均不相同，其中第一个延展星图与引理6.1的证明中提到的相同(见图3)，另外四个延展星图分别如图4~7所示。

因为 $\left|F_e\right|\le 2n-2=2\times 3-2=4$，我们只需要考虑有四条遗失边的情况。设 $t\left(0\le t\le 4\right)$ 是与x相关联的遗失边的数目，那么 $4-t$ 就是不与x相关联的遗失边的数目。如果 $t=0$，那么 $4-t=4$，则存在四条遗失边不与x相关联。由于我们已经找到了五个除了与x关联的边之外都不同的延展星图 $ES\left(x;6\right)$，所以我们可以从五个延展星图 $ES\left(x;6\right)$ 中找到一个不包含遗失边的延展星图 $ES\left(x;6\right)$。如果 $t\ne 0$，我们再分情况讨论。当 $t=1$ 时，则 $4-t=3$。如上所述，我们已经找到了五个除了与x关联的边之外都不同的延展星图 $ES\left(x;6\right)$，我们可以从这五个当中至少找到四个除了与x关联的边之外都不同的延展星图 $ES\left(x;5\right)$，这样我们就可以找到一个不包含遗失边的延展星图 $ES\left(x;5\right)$。当 $t=2$ 时，则 $4-t=2$。情况类似，我们从已经找到的五个除了与x关联的边之外都不同的延展星图 $ES\left(x;6\right)$ 当中至少找到三个除了与x关联的边之外都不同的延展星图 $ES\left(x;4\right)$，这样我们又可以找到一个不包含遗失边的延展星图 $ES\left(x;4\right)$。当 $t=3$ 时，则 $4-t=1$。情况类似，我们从已经找到的五个除了与x关联的边之外都不同的延展星图 $ES\left(x;6\right)$ 当中至少找到两个除了与x关联的边之外都不同的延展星图 $ES\left(x;3\right)$，这样我们又可以找到一个不包含遗失边的延展星图 $ES\left(x;3\right)$。当 $t=4$ 时，则 $4-t=0$。情况类似，我们从已经找到的五个除了与x关联的边之外都不同的延展星图 $ES\left(x;6\right)$ 当中至少找到一个除了与x关联的边之外都不同的延展星图 $ES\left(x;2\right)$，这样我们又可以找到一个不包含遗失边的延展星图 $ES\left(x;2\right)$。由此我们可以得出结论：在具有遗失边 $F_e$ 的 $Q_3^k-F_e$ 中存在一个延展星图 $ES\left(x;d_{Q_3^k-F_e}\left(x\right)\right)$，其中 $\left|F_e\right|\le 4$。

Figure 4. The second $ES\left(x;6\right)$ in $Q_3^k$

图4. $Q_3^k$ 的第二个延展星图 $ES\left(x;6\right)$

Figure 5. The third $ES\left(x;6\right)$ in $Q_3^k$

图5. $Q_3^k$ 的第三个延展星图 $ES\left(x;6\right)$

Figure 6. The fourth $ES\left(x;6\right)$ in $Q_3^k$

图6. $Q_3^k$ 的第四个延展星图 $ES\left(x;6\right)$

Figure 7. The fifth $ES\left(x;6\right)$ in $Q_3^k$

图7. $Q_3^k$ 的第五个延展星图 $ES\left(x;6\right)$

假设这个引理对于 $Q_{n-1}^k\left(n\ge 4,k\ge 6\right)$ 成立，即在 $Q_{n-1}^k-F_e$ 中存在一个延展星图 $ES\left(x;d_{Q_{n-1}^k-F_e}\left(x\right)\right)$，其中 $F_e$ 是遗失边集且 $\left|F_e\right|\le 2\left(n-1\right)-2=2n-4$。现在我们证明这个结论对于 $Q_n^k\left(n\ge 4,k\ge 6\right)$ 也成立，即在 $Q_n^k-F_e$ 中存在一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$，其中 $F_e$ 是遗失边集且 $\left|F_e\right|\le 2n-2$。设 $Q\left[i\right]$ 是由 $Q_n^k$ 的顶点最后一个位置 $i\left(0\le i\le k-1\right)$ 诱导的子图，则 $Q\left[i\right]$ 同构于 $Q_{n-1}^k$。设 $x=00\cdots 00=\left(0\right)$，记 $\left(0\right)$ 点在 $Q\left[0\right]$ 中。由引理5.3， $\left(0\right)$ 与两个外部邻点相邻： $00\cdots 01$ 和 $00\cdots 0\left(k-1\right)$。设 $y=00\cdots 01$， $z=00\cdots 0\left(k-1\right)$，它们分别在 $Q\left[1\right]$ 和 $Q\left[k-1\right]$ 之中。设 $F_e^i=F_e\cap E\left(Q\left[i\right]\right)$，其中 $0\le i\le k-1$， $F^{*}=F_e\cap \left(E\left(Q_n^k\right)\backslash {\displaystyle {\sum }_{i=0}^{k-1}E\left(Q\left[i\right]\right)}\right)$，那么 $F_e=F^{*}\cup F_e^0\cup \cdots \cup F_e^{k-1}$。注意到 $\left|F_e\right|\le 2n-2$，我们有 $\left|F_e^i\right|\le 2n-2$，其中 $0\le i\le k-1$。为了证明这个引理，我们首先需要在 $Q\left[0\right]-F_e^0$ 中找到一个延展星图 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$，然后找到两条分别处在 $Q\left[1\right]$ 和 $Q\left[k-1\right]$ 中的3长路 $P_y$ 和 $P_z$，我们连接 $P_y$ 和 $P_z$ 到x，然后将它们与 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$ 相结合，这样我们就在 $Q_n^k-F_e$ 中得到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。我们再考虑以下情形。

情形1 $\left|F_e^0\right|\le 2n-4$。

由归纳假设，在 $Q\left[0\right]-F_e^0\left(n\ge 3,k\ge 6\right)$ 中存在一个延展星图 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$。为方便起见，我们假设 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)=A$。如果 $xy\in F_e$，那么我们就不需要通过 $xy$ 扩展A。如果 $xy\notin F_e$，由引理5.3可知， $\kappa \left(Q\left[1\right]\right)=2n-2$。我们再考虑下列情形。

情形1.1 $\left|F_e^1\right|=2n-2$。

在这种情形下， $\left|F^{*}\right|=\left|F_e^0\right|=\left|F_e^2\right|=\cdots =\left|F_e^{k-1}\right|=0$。y有两个外部邻点 $00\cdots 02$ 和 $00\cdots 00$。注意到 $00\cdots 00=\left(0\right)=x$， $00\cdots 02\in V\left(Q\left[2\right]\right)$。设 $P_y=\langle 0000\cdots 01,0000\cdots 02,0100\cdots 02,01\left(k-1\right)0\cdots 02\rangle$， $P_z=\langle 0000\cdots 0\left(k-1\right),0100\cdots 0\left(k-1\right),0110\cdots 0\left(k-1\right),1110\cdots 0\left(k-1\right)\rangle$。因为 $\left|F_e^2\right|=\left|F_e^{k-1}\right|=0$，我们有 $V\left(P_y\right)\cap V\left(P_z\right)=\varnothing$ 且 $P_y$ 和 $P_z$ 不包含遗失边。我们连接 $P_y$ 和 $P_z$ 到x，然后将它们与A相结合，这样我们在 $Q_n^k-F_e$ 中得到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。

情形1.2 $\left|F_e^1\right|<2n-2$。

由引理5.3， $\lambda \left(Q\left[1\right]\right)=2n-2>\left|F_e^1\right|$，因此，我们可以得到 $Q\left[1\right]-F_e^1$ 是连通的。 $\left|V\left(Q\left[1\right]-F_e^1\right)\right|=\left|V\left(Q\left[1\right]\right)\right|=k^{n-1}\ge 216\left(n\ge 4,k\ge 6\right)$，我们可以在 $Q\left[1\right]-F_e^1$ 中找到一条以y开头的3长路 $P_y$，然后将它通过 $xy$ 扩展A。如果 $\left|F_e^{k-1}\right|<2n-2$，该情况与之类似，于是我们可以在 $Q\left[k-1\right]-F_e^{k-1}$ 中找到一条以z开头的3长路 $P_z$，然后将它通过 $xz$ 扩展A。如果 $\left|F_e^{k-1}\right|=2n-2$，那么 $\left|F_e^1\right|=0$，情况与情形1.1类似，我们可以找到两条3长路 $P_y$ 和 $P_z$。

情形2 $\left|F_e^0\right|=2n-3$ 且 $\left|F_e\right|=2n-3$。

在这种情形下， $\left|F^{*}\right|+\left|F_e^1\right|+\cdots +\left|F_e^{k-1}\right|=0$。 设 $y=0000\cdots 01$， $z=0000\cdots 0\left(k-1\right)$，它们分别在 $Q\left[1\right]$ 和 $Q\left[k-1\right]$ 中。我们可以找到两条不同的分别以y和z开头的3长路：

$P_y^1=\langle 0000\cdots 01,0100\cdots 01,01\left(k-1\right)0\cdots 01,02\left(k-1\right)0\cdots 01\rangle$，

$P_y^2=\langle 0000\cdots 01,0\left(k-1\right)00\cdots 01,0\left(k-1\right)\left(k-1\right)0\cdots 01,1\left(k-1\right)\left(k-1\right)0\cdots 01\rangle$，

$P_z^1=\langle 0000\cdots 0\left(k-1\right),0100\cdots 0\left(k-1\right),0110\cdots 0\left(k-1\right),1110\cdots 0\left(k-1\right)\rangle$，

$P_z^2=\langle 0000\cdots 0\left(k-1\right),0\left(k-1\right)00\cdots 0\left(k-1\right),0\left(k-1\right)\left(k-1\right)0\cdots 0\left(k-1\right),1\left(k-1\right)\left(k-1\right)0\cdots 0\left(k-1\right)\rangle$。

很显然， $P_y^1$， $P_y^2$， $P_z^1$ 和 $P_z^2$ 中除了y和z之外没有公共点。因为 $\left|F^{*}\right|+\left|F_e^1\right|+\cdots +\left|F_e^{k-1}\right|=0$，所以在 $Q\left[0\right]$ 外部不存在 $F_e$ 中的边，因此我们可以从 $P_y^1$， $P_y^2$， $P_z^1$ 和 $P_z^2$ 中选择两条不包含遗失边的3长路 $P_y$ 和 $P_z$。设f是 $F_e^0$ 中任意一个元素，并且 ${F^{\prime }}_e=F_e^0\backslash \left\{f\right\}$，那么 $\left|{F^{\prime }}_e\right|=2n-4$。由归纳假设，在 $Q\left[0\right]-{F^{\prime }}_e$ 中存在一个延展星图 $ES\left(x;d_{Q\left[0\right]-{F^{\prime }}_e}\left(x\right)\right)$。设 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)=A$。如果A中不包含f，那么我们可以在 $Q\left[0\right]-F_e^0$ 中找到一个延展星图 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$。下面我们讨论 $f\in E\left(A\right)$。

情形2.1 f与x相关联。

在这种情形下，我们通过删除A中包含f的路得到延展星图 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$。因为 $\left|F^{*}\right|+\left|F_e^1\right|+\cdots +\left|F_e^{k-1}\right|=0$，则我们可以从 $P_y^1$， $P_y^2$， $P_z^1$ 和 $P_z^2$ 中选择两条不包含遗失边的3长路 $P_y$ 和 $P_z$。我们连接 $P_y$ 和 $P_z$ 到x，然后将它们与 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$ 相结合，因此，我们在 $Q_n^k-F_e$ 中就得到了一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。

情形2.2 f不与x相关联。

设 $P_u$ 是一条以u开头的3长路，同时假设它包含f，那么u与x相邻。由定义5.1，记 $N_{Q_n^k}\left(x\right)=\left\{u_0{u}_1\cdots \left(u_i+1\right)\cdots u_{n-1},u_0{u}_1\cdots \left(u_i-1\right)\cdots u_{n-1}|u_i=0,0\le i\le n-1\right\}$，并且 $u\in V\left(Q\left[0\right]\right)$。不失一般性，设 $u=100\cdots 00$。由引理5.3，u有两个外部邻点 $100\cdots 01$ 和 $100\cdots 0\left(k-1\right)$，它们分别在 $Q\left[1\right]$ 和 $Q\left[k-1\right]$ 中。因为在 $Q\left[0\right]$ 外部不存在 $F_e$ 中的边，所以存在一个点 $u^{\prime }$ 使得 $u^{\prime }$ 是u的外部邻点，同时 $u{u}^{\prime }\notin F_e$。因此我们只需要找到一条以 $u^{\prime }$ 开头的2长路。不失一般性，假设 $u^{\prime }\in V\left(Q\left[1\right]\right)$ 或者 $u^{\prime }\in V\left(Q\left[k-1\right]\right)$。

情形2.2.1 $u^{\prime }\in V\left(Q\left[1\right]\right)$。

在这种情形下， $u^{\prime }=100\cdots 01$。注意到 $P_y^1=\langle 0000\cdots 01,0100\cdots 01,01\left(k-1\right)0\cdots 01,02\left(k-1\right)0\cdots 01\rangle$， $\left|F_e^1\right|=0$，于是我们可以从 $Q\left[1\right]$ 中找到一条以 $u^{\prime }$ 开头的不包含遗失边的2长路： $P_{u^{\prime }}=\langle 100\cdots 01,1\left(k-1\right)0\cdots 01,2\left(k-1\right)0\cdots 01\rangle$。注意到 $y\notin V\left(P_{u^{\prime }}\right)$，且 $V\left(P_y^1\right)\cap V\left(P_{u^{\prime }}\right)=\varnothing$，因此我们连接 $P_{u^{\prime }}$ 到u即可得到一条3长路 $P_u$，然后连接 $P_u$， $P_y^1$ 和 $P_z$ 到x，然后将它们与A相结合，于是可以在 $Q_n^k-F_e$ 中

得到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。

情形2.2.2 $u^{\prime }\in V\left(Q\left[k-1\right]\right)$。

在这种情形下， $u^{\prime }=100\cdots 0\left(k-1\right)$。注意到 $P_z^1=\langle 0000\cdots 0\left(k-1\right),0100\cdots 0\left(k-1\right),0110\cdots 0\left(k-1\right),1110\cdots 0\left(k-1\right)\rangle$， $\left|F_e^{k-1}\right|=0$，于是我们可以从 $Q\left[k-1\right]$ 中找到一条以 $u^{\prime }$ 开头的不包含遗失边的2长路： $P_{u^{\prime }}=\langle 100\cdots 0\left(k-1\right),1\left(k-1\right)0\cdots 0\left(k-1\right),2\left(k-1\right)0\cdots 0\left(k-1\right)\rangle$。注意到 $z\notin V\left(P_{u^{\prime }}\right)$，且 $P_z^1$ 与 $P_{u^{\prime }}$ 之间没有公共点。因此我们连接 $P_{u^{\prime }}$ 到u即可得到一条3长路 $P_u$，然后连接 $P_u$， $P_y$ 和 $P_z^1$ 到x，然后将它们与A相结合，于是可以在 $Q_n^k-F_e$ 中得到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。

情形3 $\left|F_e^0\right|=2n-3$ 且 $\left|F_e\right|=2n-2$。

注意到 $\left|F^{*}\right|+\left|F_e^1\right|+\cdots +\left|F_e^{k-1}\right|=1$。 设 $y=000\cdots 01$， $z=000\cdots 0\left(k-1\right)$，它们分别在 $Q\left[1\right]$ 和 $Q\left[k-1\right]$ 中。我们可以找到两条不同的分别以y和z开头的3长路：

$P_y^1=\langle 0000\cdots 01,0100\cdots 01,01\left(k-1\right)0\cdots 01,02\left(k-1\right)0\cdots 01\rangle$，

$P_y^2=\langle 0000\cdots 01,0\left(k-1\right)00\cdots 01,0\left(k-1\right)\left(k-1\right)0\cdots 01,1\left(k-1\right)\left(k-1\right)0\cdots 01\rangle$，

$P_z^1=\langle 0000\cdots 0\left(k-1\right),0100\cdots 0\left(k-1\right),0110\cdots 0\left(k-1\right),1110\cdots 0\left(k-1\right)\rangle$，

$P_z^2=\langle 0000\cdots 0\left(k-1\right),0\left(k-1\right)00\cdots 0\left(k-1\right),0\left(k-1\right)\left(k-1\right)0\cdots 0\left(k-1\right),1\left(k-1\right)\left(k-1\right)0\cdots 0\left(k-1\right)\rangle$。

很显然， $P_y^1$， $P_y^2$， $P_z^1$ 和 $P_z^2$ 之间除了y和z之外没有公共点。如果 $\left|F_e^1\right|+\left|F_e^2\right|\cdots +\left|F_e^{k-1}\right|=1$，则在 $Q_n^k-V\left(Q\left[0\right]\right)$ 中最多存在 $F_e$ 中的一条边。因此，我们可以从 $P_y^1$， $P_y^2$， $P_z^1$ 和 $P_z^2$ 中选择两条不包含遗失边的3长路。如果 $\left|F^{*}\right|=1$，那么 $\left|F_e^1\right|+\cdots +\left|F_e^{k-1}\right|=0$。在这种情形下，如果 $\left|F^{*}\cap \left\{xy,xz\right\}\right|=0$，那么我们从 $Q_n^k\left[V\left(P_y^1\right)\cup \left\{x\right\}\right]$， $Q_n^k\left[V\left(P_y^2\right)\cup \left\{x\right\}\right]$， $Q_n^k\left[V\left(P_z^1\right)\cup \left\{x\right\}\right]$ 和 $Q_n^k\left[V\left(P_z^2\right)\cup \left\{x\right\}\right]$ 中选择两条不包含遗失边的3长路。如果 $\left|F^{*}\cap \left\{xy,xz\right\}\right|=1$，那么我们从 $Q_n^k\left[V\left(P_y^1\right)\cup \left\{x\right\}\right]$， $Q_n^k\left[V\left(P_y^2\right)\cup \left\{x\right\}\right]$， $Q_n^k\left[V\left(P_z^1\right)\cup \left\{x\right\}\right]$ 和 $Q_n^k\left[V\left(P_z^2\right)\cup \left\{x\right\}\right]$ 中选择一条不包含遗失边的3长路。设f是 $F_e^0$ 中任意一个元素，且设 ${F^{\prime }}_e=F_e^0\backslash \left\{f\right\}$，那么 $\left|{F^{\prime }}_e\right|=2n-4$。由归纳假设，在 $Q\left[0\right]-{F^{\prime }}_e$ 中存在一个延展星图 $ES\left(x;d_{Q\left[0\right]-{F^{\prime }}_e}\left(x\right)\right)$。设 $ES\left(x;d_{Q\left[0\right]-{F^{\prime }}_e}\left(x\right)\right)=A$。如果A中不包含f，那么我们可以在 $Q\left[0\right]-F_e^0$ 中找到一个延展星图 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)=A$。下面我们讨论 $f\in E\left(A\right)$。

情形3.1 f与x相关联。

我们通过删除包含f的路得到一个延展星图 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$。假设 $\left|F^{*}\right|=0$，那么 $xy\notin F_e$， $xz\notin F_e$。因为 $\left|F^{*}\right|+\left|F_e^1\right|+\cdots +\left|F_e^{k-1}\right|=1$，我们从 $P_y^1$， $P_y^2$， $P_z^1$ 和 $P_z^2$ 中选择两条不包含遗失边的3长路 $P_y$ 和 $P_z$。我们连接 $P_y$ 和 $P_z$ 到x，然后将它们与 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$ 相结合。因此，我们可以在 $Q_n^k-F_e$ 中找到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。假设 $\left|F^{*}\right|=1$。如果 $\left|F^{*}\cap \left\{xy,xz\right\}\right|=0$，那么我们从 $P_y^1$， $P_y^2$， $P_z^1$ 和 $P_z^2$ 中选择两条3长路 $P_y$ 和 $P_z$。我们将 $P_y$ 和 $P_z$ 这两条路连接到x，然后将它们与 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$ 相结合。因此，我们可以在 $Q_n^k-F_e$ 中得到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。如果 $\left|F^{*}\cap \left\{xy,xz\right\}\right|=1$。设 $F^{*}=\left\{xy\right\}$ 或 $\left\{xz\right\}$。我们通过删除包含 $xy$ 或 $xz$ 的路得到一个延展星图 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$。我们从 $P_y$ 和 $P_z$ 中选择一条不包含遗失边的路连接到x，然后将它与 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$ 相结合。因此，我们可以在 $Q_n^k-F_e$ 中得到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。

情形3.2 f与x不相关联。

设 $P_u$ 是一条以u开头的3长路，且假设它包含f，那么u与x相邻。由定义5.1，记 $N_{Q_n^k}\left(x\right)=\left\{u_0{u}_1\cdots \left(u_i+1\right)\cdots u_{n-1},u_0{u}_1\cdots \left(u_i-1\right)\cdots u_{n-1}|u_i=0,0\le i\le n-1\right\}$ 且 $u\in V\left(Q\left[0\right]\right)$。不失一般性，设 $u=100\cdots 00$。由引理5.3，u有两个外部邻点 $100\cdots 01$ 和 $100\cdots 0\left(k-1\right)$，它们分别在 $Q\left[1\right]$ 和 $Q\left[k-1\right]$ 中。因为在 $Q\left[0\right]$ 外部存在 $F_e$ 中的一条边，所以存在一个点 $u^{\prime }$ 使得 $u^{\prime }$ 是u的外部邻点，同时 $u{u}^{\prime }\notin F_e$。因为 $\left|F^{*}\right|+\left|F_e^1\right|+\cdots +\left|F_e^{k-1}\right|=1$。设 $\left|F^{*}\right|=0$，那么 $\left|F_e^1\right|+\cdots +\left|F_e^{k-1}\right|=1$。我们只需要找到一条以 $u^{\prime }$ 开头的2长路。不失一般性，假设 $u^{\prime }\in V\left(Q\left[1\right]\right)$ 或者 $u^{\prime }\in V\left(Q\left[k-1\right]\right)$。

情形3.2.1 $u^{\prime }\in V\left(Q\left[1\right]\right)$。

在这种情形下， $u^{\prime }=100\cdots 01$。注意到 $P_y^1=\langle 0000\cdots 01,0100\cdots 01,01\left(k-1\right)0\cdots 01,02\left(k-1\right)0\cdots 01\rangle$， $P_y^2=\langle 0000\cdots 01,0\left(k-1\right)00\cdots 01,0\left(k-1\right)\left(k-1\right)0\cdots 01,1\left(k-1\right)\left(k-1\right)0\cdots 01\rangle$，我们可以找到两条以 $u^{\prime }$ 开头的2长路：

$P_{u^{\prime }}^1=\langle 100\cdots 01,1\left(k-1\right)0\cdots 01,2\left(k-1\right)0\cdots 01\rangle$，

$P_{u^{\prime }}^2=\langle 100\cdots 01,110\cdots 01,120\cdots 01\rangle$。

很显然， $P_y^1$， $P_y^2$， $P_{u^{\prime }}^1$ 和 $P_{u^{\prime }}^2$ 中除了 $u^{\prime }$ 和y之外没有公共点。因为在 $Q\left[0\right]$ 之外最多存在 $F_e$ 中的一条边，我们可以从 $P_{u^{\prime }}^1$ 和 $P_{u^{\prime }}^2$ 中选择一条不包含遗失边的2长路 $P_{u^{\prime }}$。我们连接 $P_{u^{\prime }}$ 到u得到一条3长路 $P_u$，然后连接 $P_u$， $P_y$ 和 $P_z$ 到x，并且将它们与 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$ 相结合。因此，我们可以在 $Q_n^k-F_e$ 中找到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。

假设 $u^{\prime }\in V\left(Q\left[k-1\right]\right)$。这里， $u^{\prime }=100\cdots 0\left(k-1\right)$。注意到 $P_z^1=\langle 0000\cdots 0\left(k-1\right),0100\cdots 0\left(k-1\right),0110\cdots 0\left(k-1\right),1110\cdots 0\left(k-1\right)\rangle$， $P_z^2=\langle 0000\cdots 0\left(k-1\right),0\left(k-1\right)00\cdots 0\left(k-1\right),0\left(k-1\right)\left(k-1\right)0\cdots 0\left(k-1\right),1\left(k-1\right)\left(k-1\right)0\cdots 0\left(k-1\right)\rangle$，我们可以找到两条以 $u^{\prime }$ 开头的2长路：

$P_{u^{\prime }}^1=\langle 100\cdots 0\left(k-1\right),1\left(k-1\right)0\cdots 0\left(k-1\right),2\left(k-1\right)0\cdots 0\left(k-1\right)\rangle$，

$P_{u^{\prime }}^2=\langle 100\cdots 0\left(k-1\right),110\cdots 0\left(k-1\right),120\cdots 0\left(k-1\right)\rangle$。

很显然， $P_z^1$， $P_z^2$， $P_{u^{\prime }}^1$ 和 $P_{u^{\prime }}^2$ 中除了 $u^{\prime }$ 和z之外没有公共点。因为在 $Q\left[0\right]$ 之外最多存在 $F_e$ 中的一条边，因此 $P_{u^{\prime }}^1$ 或者 $P_{u^{\prime }}^2$ 不包含遗失边。我们从 $P_{u^{\prime }}^1$ 和 $P_{u^{\prime }}^2$ 中选择一条不包含遗失边的2长路 $P_{u^{\prime }}$。我们连接 $P_{u^{\prime }}$

到u即可得到一条3长路 $P_u$，然后连接 $P_u$， $P_y$ 和 $P_z$ 到x，并且将它们与延展星图 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)$ 相结合。因此，我们可以在 $Q_n^k-F_e$ 中找到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。

假设 $\left|F^{*}\right|=1$，那么 $\left|F_e^1\right|+\left|F_e^2\right|+\cdots +\left|F_e^{k-1}\right|=0$。 因此，存在一个点 $u^{\prime }$ 使得 $u^{\prime }$ 是u的外部邻点且 $u{u}^{\prime }\notin F_e$。不失一般性，假设 $u^{\prime }\in V\left(Q\left[1\right]\right)$。与情形3.2.1类似，我们可以在 $Q_n^k-F_e$ 中找到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。

情形4 $\left|F_e^0\right|=2n-2$。

在这种情形下， $\left|F^{*}\right|+\left|F_e^1\right|+\left|F_e^2\right|+\cdots +\left|F_e^{k-1}\right|=0$。设f， $f^{\prime }$ 是 $F_e^0$ 中任意两个元素，且 ${F^{\prime }}_e=F_e^0\backslash \left\{f,f^{\prime }\right\}$，那么 $\left|{F^{\prime }}_e\right|=2n-4$。由归纳假设，我们可以在 $Q\left[0\right]-{F^{\prime }}_e$ 中存在一个延展星图 $ES\left(x;d_{Q\left[0\right]-{F^{\prime }}_e}\left(x\right)\right)$。设 $ES\left(x;d_{Q\left[0\right]-{F^{\prime }}_e}\left(x\right)\right)=A$。

情形4.1 A中不包含f和 $f^{\prime }$。

我们可以在 $Q\left[0\right]-F_e^0$ 中找到一个延展星图 $ES\left(x;d_{Q\left[0\right]-F_e^0}\left(x\right)\right)=A$。注意到 $\left|F_e^0\right|=2n-2$ 且 $\left|F_e\right|\le 2n-2$，那么在 $Q\left[1\right]$ 和 $Q\left[k-1\right]$ 中不存在 $F_e$ 中的边。因此，我们可以在 $Q\left[1\right]$ 中找到一条以y开头的3长路 $P_y$，然后将 $P_y$ 与x相连，然后将它与A相结合。 $xz$ 的情况与此类似。因此，我们可以在 $Q_n^k-F_e$ 中找到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$。

情形4.2 A中包含f或 $f^{\prime }$。

不失一般性，我们假设A中包含f。 现在我们讨论f是否与x相关联。如果f与x相关联，证明与情形2.1类似。如果f不与x相关联，证明与情形2.2类似。

情形4.3 A中包含f和 $f^{\prime }$。

如果f和 $f^{\prime }$ 都与x相关联，那么我们可以通过删除包含f和 $f^{\prime }$ 的路得到一个延展星图 $ES\left(x;d_{Q\left[0\right]-\left\{{F^{\prime }}_e\cup f\cup f^{\prime }\right\}}\left(x\right)\right)$，接下来的证明与情形3.1类似。如果 $\left\{f,f^{\prime }\right\}$ 中仅有一个与x相关联，不失一般性，设 $f^{\prime }$ 与x相关联，f不与x相关联。我们可以在 $Q\left[0\right]-\left\{{F^{\prime }}_e\cup f^{\prime }\right\}$ 中找到一个延展星图 $ES\left(x;d_{Q\left[0\right]-\left\{{F^{\prime }}_e\cup f^{\prime }\right\}}\left(x\right)\right)$，接下来的证明与情形2.2类似。如果f和 $f^{\prime }$ 都不与x相关联，那么我们考虑f和 $f^{\prime }$ 是否属于同一条路。如果f和 $f^{\prime }$ 都属于同一条路，证明过程与情形2.2类似。现在我们假设f和 $f^{\prime }$ 属于A中不同的路。设 $P_u$ 是一条以u开头3长路并且假设它包含f。设 $P_v$ 是一条以v开头的3长路并且假设它包含 $f^{\prime }$。由引理5.3，每个u和v分别有两个外部邻点且在不同的子图中。假设u和v的一个外部邻点分别是 $u^{\prime }$ 和 $v^{\prime }$，其中 $u^{\prime }\in Q\left[i\right]$， $v^{\prime }\in Q\left[j\right]$， $i,j\in \left\{1,k-1\right\}$ 且 $i\cancel{=}j$。注意到 $\left|F_e^0\right|=2n-2$， $\left|F_e\right|\le 2n-2$，那么在 $Q\left[0\right]$ 之外不存在 $F_e$ 中的边，因此我们可以分别在 $Q\left[i\right]$ 和 $Q\left[j\right]$ 中找到一条以 $u^{\prime }$ 和 $v^{\prime }$ 开头的2长路 $P_{u^{\prime }}$ 和 $P_{v^{\prime }}$，然后将它们分别与 $u{u}^{\prime }$ 和 $v{v}^{\prime }$ 相连，我们就得到了不包含遗失边的3长路 $P_u$ 和 $P_v$。因此，我们就完成了在 $Q_n^k-F_e$ 中找到一个延展星图 $ES\left(x;d_{Q_n^k-F_e}\left(x\right)\right)$ 的证明。

定理6.2 设 $F_e$ 是k元n立方体 $Q_n^k\left(n\ge 3,k\ge 6\right)$ 中任意边子集且 $\left|F_e\right|\le 2n-2$。对 $Q_n^k$ 中的每个点x， $Q_n^k-F_e$ 有强局部诊断性，其中 $F_e$ 的个数是最优的。

证明由引理4.6和6.2，在 $Q_n^k-F_e$ 中，每个点x的局部诊断度等于它的度，且 $n\ge 3$， $k\ge 6$， $\left|F_e\right|\le 2n-2$。由引理4.8和4.9， $Q_n^k-F_e$ 有强局部诊断性。现在我们证明 $F_e$ 的个数是最优的。

接下来我们举例说明当k元n立方体 $Q_n^k$ 存在 $2n-1$ 条遗失边时不能保证有强局部诊断性。因为 $Q_n^k$ 是一个点传递图，不失一般性，假设 $x=00\cdots 00\in V\left(Q_n^k\right)$。我们假设在 $Q_n^k$ 中存在 $2n-1$ 条遗失边F都与x相关联(见图8)，那么在 $Q_n^k-F$ 中x的度就变成了1，即 $d_{Q_n^k-F}\left(x\right)=1$。很容易知道y是x在 $d_{Q_n^k-F}\left(x\right)$ 中唯一的邻点。设 $F_1=\left(\left\{y\right\}\cup N\left(y\right)\right)\backslash \left\{x\right\}$， $F_2=N\left(y\right)$，此时 $\left|F_1\right|=\left|F_2\right|=2n$。显然， $V\left(Q_n^k-F_e\right)\backslash \left(F_1\cup F_2\right)$ 和 $F_1△F_2$ 之间是没有边的。由定理3.1和引理4.8， $\left(F_1,F_2\right)$ 不满足条件(1)~(3)，并且在 $Q_n^k-F$ 中y点在MM*模型下不是2n局部诊断的。然而， $d_{Q_n^k-F}\left(y\right)=2n$，故在 $Q_n^k-F$ 中y点的局部诊断度(少于2n)不等于它的度(等于2n)。因此，y没有强局部诊断性。故当k元n立方体 $Q_n^k$ 有 $2n-1$ 条遗失边时，它不具有强局部诊断性了。

Figure 8. Illustration of the proof in Theorem 6.2

图8. 定理6.2的证明

7. 结论

在这篇文章中，我们研究了k元n立方体 $Q_n^k\left(n\ge 3,k\ge 6\right)$ 在MM*模型下的局部诊断度。由强局部诊断性的定义 [8]，我们证明了k元n立方体 $Q_n^k$ 具有强局部诊断性，即使存在高达 $2n-2$ 条遗失边，它仍保持强局部诊断性。所以，在k元n立方体 $Q_n^k\left(n\ge 3,k\ge 6\right)$ 的遗失边数不超过 $2n-2$ 的条件下，它的诊断度等于每个处理器剩余度的最小值。

致谢

本论文是在我的导师王世英教授的亲切关怀和认真指导下完成的。他严肃的科学态度，严谨的治学精神，精益求精的工作作风，深深地激励着我。从课题的选择到项目的最终完成，王老师都始终给予我细心的指导和不懈的支持。在写论文的过程中，王教授不仅在学业上给我精心的指导，同时还在思想、生活上给我无微不至的关怀，在此谨向王老师致以诚挚的谢意和崇高的敬意。同时，感谢与我并肩作战的师兄、师姐以及同门们，感谢关心我，支持我的朋友们，感谢学校领导、老师们，感谢你们给予我的帮助与关怀，谢谢！