有缺失边的n维增强超立方体在MM*模型下的局部可诊断性 Local Diagnosability of n-Dimensional Enhanced Hypercubes with Missing Edges under the MM* Model

doi:10.12677/AAM.2022.112079

Advances in Applied Mathematics
Vol. 11 No. 02 ( 2022 ), Article ID: 48720 , 13 pages
10.12677/AAM.2022.112079

有缺失边的n维增强超立方体在MM*模型下的局部可诊断性

王世英^*，张雪芳，赵丽娜

●How to Cite this Article

山西师范大学，数学与计算机科学学院，山西太原

收稿日期：2022年1月11日；录用日期：2022年2月9日；发布日期：2022年2月16日

摘要

多重处理器系统的诊断性在互联网的可靠性中扮演着重要的角色。n维增强超立方体 $Q_{n, k}$ 是由n维超立方体 $Q_{n}$ 添加一些互补边得到的。n维增强超立方体 $Q_{n, k}$ 有许多好的性质。这篇文章中，我们首先证明了在MM*模型下 $Q_{n, k}$ 具有强局部诊断性，然后证明了在MM*模型下 $Q_{n, k}$ 即使存在 $n - 1$ 条缺失边时仍具有强局部诊断性，并且证明了缺失边的数目 $n - 1$ 是最优值。

关键词

互连网络，强局部诊断度，n维增强超立方体，延展星结构，MM*模型

Local Diagnosability of n-Dimensional Enhanced Hypercubes with Missing Edges under the MM* Model

Shiying Wang^*, Xuefang Zhang, Lina Zhao

College of Mathematics and Information Science, Shanxi Normal University, Taiyuan Shanxi

Received: Jan. 11^th, 2022; accepted: Feb. 9^th, 2022; published: Feb. 16^th, 2022

ABSTRACT

The diagnosability of multiprocessor systems plays an important role in the reliability of the Internet. The n-dimensional enhanced hypercube $Q_{n, k}$ is obtained by adding some complementary edges to n-dimensional hypercubes. The n-dimensional enhanced hypercube $Q_{n, k}$ has many good properties. In this paper, we prove $Q_{n, k}$ has the strong local diagnosability property under the MM* model. Then we prove that $Q_{n, k} (n \leq 6)$ keeps the strong local diagnosability property even if there exist $n - 1$ missing edges in it under the MM* model and the result is optimal with respect to the number of missing edges.

Keywords:Interconnection Networks, Strong Local Diagnosability, N-Dimensional Enhanced Hypercubes, Extended Star Structure, MM* Model

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

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

1. 引言

多处理器系统一般以某种互联网络作为拓扑结构。因此，研究互联网络的性能对整个多处理器系统有着重大意义。互联网络可用图表示，那么网络拓扑结构的性能就可以通过图的性质和参数来进行度量。由于多处理系统中包含处理器数目不断增多，处理器出现故障是不可避免的。为了让系统在出现故障处理器的情况下仍然可以正常工作，处理器故障识别被提出来并承担了这一重要工作。这一识别过程被称为系统诊断 [1]。一些处理器在诊断时可能会出现故障，所以发现哪些处理器发生故障是非常重要的。在之前的研究中，研究者们已经提出许多系统诊断模型，其中被广泛使用的是比较模型(MM模型)。MM模型是由Maeng和Malek首次提出 [2]。之后，Sengupta和Dahbura [3] 提出MM*模型，它是MM模型的一个特例。在MM*模型中，一个节点必须测试它的每一对相邻节点。Sengupta和Dahbura在MM*模型下为有n个处理器的一般诊断系统提出了一个 $O (n^{5})$ 诊断算法 [4]。在故障处理器的数量不超过t的情况下，如果所有故障的处理器可以被识别出来并且不被替换，我们就称这个系统是t-可诊断的。一个系统G的诊断度 $t (G)$ 是使得G是t-可诊断的t的最大值 [5]。

在文献 [6] 中，Hau和Tan提出了一种测量多重处理器系统G的诊断度，即G的局部诊断度。这种新的测量方法研究了每个处理器的局部可诊断性而不是整个系统的可诊断性。如果我们只考虑全局故障或无故障状态，那就会失去这个系统的一部分细节。在 [7] 中，Chiang和Tan提出了延展星结构。这是一种有效的局部结构为了确保每个节点的可诊断性，并给出了MM模型下确定节点可诊断性的充分条件。他们发现G的局部可诊断性和传统可诊断性之间存在着非常紧密的联系。如果系统G中每个节点的局部可诊断性都等于它在G中的度，那么就说这个系统G有强局部可诊断性。在此基础上，强局部可诊断性被广泛研究。在 [8] 中，Chiang等人研究了n维星图的可诊断性，也证明了它在具有 $n - 3$ 条缺失边的情况下仍然保持强的局部可诊断性。除此之外，Cheng等人也把上述结果扩展到了由置换树生成的Cayley图 [9]， $(n, k)$ 星图和2树生成的Cayley图 [10] 中，它们仍然保持强的局部可诊断性。在过去的许多年里，人们提出了大量的互联网络拓扑结构。在拓扑结构中，超立方体因其结构规则、对称、直径小、连通性强等优良特性而备受关注 [11] [12] [13] [14]。由于超立方体的重要性，许多它的变体也被提出。比如广义超立方体，扭曲超立方体，平衡超立方体，折叠超立方体和增强超立方体。增强超立方体是在超立方体结构上添加一些互补边扩展得到的，比超立方体具有更多好的性质 [15] [16] [17]。折叠超立方体是增强超立方体在 $k = 1$ 时的特殊情况。在1999年，Wang [18] 研究了超立方体和增强超立方体在MM*模型下的可诊断性。在2019年，Sabir [19] 等人研究了增强超立方体的额外连通度。在2021年，Wang [5] 等人研究了n维超立方体和折叠超立方体在MM*模型下的局部可诊断性，证明出超立方体即使存在 $n - 1$ 条缺失边仍然保持强局部可诊断性，并且缺失边的数量达到最优；还证明了折叠超立方体即使存在高达 $n - 2$ 条缺失边仍然保持强局部可诊断性，它的缺失边数量也是最优的。

在这篇文章中，我们首先证明了增强超立方体 $Q_{n, k}$ 在比较模型下的强局部可诊断性是 $n + 1$ 。然后证明了增强超立方体 $Q_{n, k}$ 在MM*模型下即使存在 $n - 1$ 条缺失边仍然保持强局部可诊断性，并且缺失边的数量是最优的。

2. 基本概念

一个多重处理器系统通常用一个无向简单图 $G = (V, E)$ 来表示，其中顶点集 $V (G)$ (节点)表示处理器，边集 $E (G)$ (链路)表示通信链接。在这个简单图G中， $d_{G} (v)$ 表示顶点v的度，即G中一个顶点v在G里相关联的边数。图G中每个顶点v，它的邻集 $N_{G} (v)$ 是所有与v相关联的顶点组成的集合。设u是v相关联的邻点，那么 $u \in N_{G} (v)$ 。一个图G被定义为是k-正则的当且仅当对于G中每个点v都满足 $d_{G} (v) = k$ 。我们用 $P = 〈 v_{0}, v_{1}, \dots, v_{n} 〉$ 来表示一条从 $v_{0}$ 开始 $v_{n}$ 结束的路，并且它被定义为一条n长路。图G的连通度 $κ (G)$ 是把G变成一个不连通图(或当G是完全图时仅一个点所需移除)的顶点最小数量。G中顶点的最小度用 $δ (G)$ 表示。图G的边连通度 $λ (G)$ 是把G变成一个不连通图的边的最小数目。假设 $V^{'}$ 是顶点集V的一个非空集合， $G [V^{'}]$ 表示G中由 $V^{'}$ 导出的子图，其中子图的边集是由每条边的两个端点都在 $V^{'}$ 中的边组成的。我们说一个图 $G_{1}$ 是同构于另一个图 $G_{2}$ (表示为 $G_{1} ≅ G_{2}$ )的，当且仅当存在一个一一映射 $φ : V (G_{1}) \to V (G_{2})$ 使得对于任意两个点 $u, v \in V (G_{1}), u v \in E (G_{1})$ 有 $φ (u) φ (v) \in E (G_{2})$ 。在这篇文章中，如果我们定义顶点 $x = u_{1} u_{2} \dots u_{i - 1} u_{i} u_{i + 1} \dots u_{n}$ ，则顶点 $x^{i} = u_{1} u_{2} \dots u_{i - 1} {\bar{u}}_{i} u_{i + 1} \dots u_{n}$ ，其中 $i \in {1, 2, \dots, n}$ 表示这两个点x和 $x^{i}$ 的二进制字符串只有第i个位置不同。文中其它未定义而直接使用的符号和术语参见文献 [20]。

增强超立方体

增强超立方体 $Q_{n, k}$ 的每个顶点都可以用一个n位的二进制字符串来表示。两个顶点相邻当且仅当它们n个位置中只有一位不同，或者n个位置中从第k个位置开始到最后一个位置都不相同。众所周知，折叠超立方体 $F Q_{n}$ 是增强超立方体 $k = 1$ 时的特殊情况，并且该超立方体已经得到了大量研究。尽管增强超立方体已经被证明有许多优点并显示出其潜在的应用前景，但它的许多拓扑特性仍是未知的，这阻碍了增强超立方体在关键领域的进一步应用。近年来对 $Q_{n, k} (1 \leq k \leq n - 1)$ 的研究取得了丰硕的成果。在 [16] 中，当 $k = 2$ 时 $Q_{n, k}$ 中任意两个不同顶点之间存在 $n + 1$ 条内部不相交路径，并且连通度 $κ (Q_{n, k})$ 和边连通度 $λ (Q_{n, k})$ 都是 $n + 1$ 。

定义2.1 [16] n维增强超立方体 $Q_{n, k} (1 \leq k \leq n - 1)$ ，它的顶点集 $V (Q_{n, k}) = {u_{1} u_{2} \dots u_{n} : u_{i} \in {0, 1}; 1 \leq i \leq n}$ 。当顶点v满足下面其中一个条件时，两个点 $u = u_{1} u_{2} \dots u_{n}$ 和v相邻：

(1) $v = u_{1} \dots u_{i - 1} {\bar{u}}_{i} u_{i + 1} \dots u_{n}, 1 \leq i \leq n$ ；

(2) $v = u_{1} \dots u_{k - 1} {\bar{u}}_{k} {\bar{u}}_{k + 1} \dots {\bar{u}}_{n}$ (见图1)。

定理 2.1 [16] 增强超立方体 $Q_{n, k} (1 \leq k \leq n - 1)$ 可以沿着第 $i (1 \leq i \leq n)$ 个位置被分解为两个不同的子图。我们分别用 $Q_{n, k}^{i : 0}$ (即 $Q_{n, k}^{0}$ )和 $Q_{n, k}^{i : 1}$ (即 $Q_{n, k}^{1}$ )来表示这两个子图。根据分解的定义，我们可以得到，当 $i < k$ 时， $Q_{n, k}^{0}$ 和 $Q_{n, k}^{1}$ 是两个 $n - 1$ 维的增强超立方体，且 $Q_{n, k} = Q_{n, k}^{0} \cup Q_{n, k}^{1}$ ； $i \geq k$ 时， $Q_{n, k}^{0}$ 和 $Q_{n, k}^{1}$ 是两个 $n - 1$ 维的超立方体，且 $Q_{n, k} = Q_{n, k}^{0} \cup Q_{n, k}^{1}$ 。一个顶点 $x = u_{1} u_{2} \dots u_{n}$ 属于 $Q_{n, k}^{0}$ 当且仅当第i个位置满足 $u_{i} = 0$ ；类似地，x属于 $Q_{n, k}^{1}$ 当且仅当第i个位置满足 $u_{i} = 1$ (见图2)。

Figure 1. The enhanced hypercube $Q_{2, 1}$ and $Q_{3, 1}$

图1. 增强超立方体 $Q_{2, 1}$ 和 $Q_{3, 1}$

Figure 2. The enhanced hypercube $Q_{3, 2}$

图2. 增强超立方体 $Q_{3, 2}$

定理 2.2 [21] 折叠超立方体 $F Q_{n}$ 是增强超立方体的扩展，是增强超立方体 $k = 1$ 的特殊情况。

定理 2.3 [16] 对于增强超方体 $Q_{n, k}$ ，当 $i < k$ 时， $Q_{n, k}^{i : 0}$ 和 $Q_{n, k}^{i : 1}$ 同构于 $Q_{n - 1, k - 1}$ ；当 $i \geq k$ 时， $Q_{n, k}^{i : 0}$ 和 $Q_{n, k}^{i : 1}$ 同构于 $Q_{n - 1}$ 。

定理 2.4 [18] 超立方体 $Q_{n}$ 满足下列性质：

(1) $Q_{n}$ 是n-正则的， $| V (Q_{n}) | = 2^{n}$ ， $| E (Q_{n}) | = n 2^{n - 1}$ 。

(2) $κ (Q_{n}) = λ (Q_{n}) = n$ 。

(3) $Q_{n}$ 是点传递的和边传递的。

(4) $Q_{n}$ 可以按照某个 $i (1 \leq i \leq n)$ 位置分解为两个子图 $Q_{n}^{i : 1}$ (即 $Q_{n}^{1}$ )和 $Q_{n}^{i : 0}$ (即 $Q_{n}^{0}$ )。

(5) $Q_{n}^{1}$ 和 $Q_{n}^{0}$ 都同构于 $Q_{n - 1}$ 。

定理 2.5 [5] 增强超立方体 $Q_{n, k}$ 满足下列性质：

(1) $Q_{n, k}$ 是 $n + 1$ 正则的， $κ (Q_{n, k}) = λ (Q_{n, k}) = n + 1 (n \geq 1)$ 。

(2)当 $i \geq k$ 时， $Q_{n, k}^{j} (j \in {0, 1})$ 中每个点仅有的两个外部邻域都在另一个子图中；当 $i < k$ 时， $Q_{n, k}^{j} (j \in {0, 1})$ 中每个点仅有的一个外部邻域也在另一个子图中。

(3) $Q_{n, k}^{j} (j \in {0, 1})$ 中任意顶点的外部邻域都在另一个子图。

(4) $Q_{n, k}$ 是点传递的和边传递的。

定理2.6 [5] 令 $F_{e}$ 是 $F Q_{n} (n \geq 6)$ 中任意缺失边集， $| F_{e} | \leq n - 1$ 。 $F Q_{n} - F_{e}$ 中存在一个延展星图 $E S (x; d_{F Q_{n} - F_{e}} (x))$ ，其中 $x \in V (F Q_{n})$ 。

定理 2.7 [5] 令 $F_{e}$ 是 $Q_{n} (n \geq 6)$ 中任意缺失边集， $| F_{e} | \leq n - 2$ 。 $Q_{n} - F_{e}$ 中存在一个延展星图 $E S (x; d_{Q_{n} - F_{e}} (x))$ ，其中 $x \in V (Q_{n})$ 。

定理 2.8 [18] 折叠超立方体 $F Q_{n}$ 满足下列性质：

(1) $F Q_{n}$ 是 $n + 1$ 正则的， $| V (F Q_{n}) | = 2^{n}$ ， $| E (F Q_{n}) | = (n + 1) 2^{n - 1}$ 。

(2) $F Q_{n}$ 是点传递的和边传递的。

(3) $κ (F Q_{n}) = λ (F Q_{n}) = n + 1$ 。

(4) $F Q_{n}$ 可以沿某 $i (1 \leq i \leq n)$ 位分解为两个子图 $F Q_{n}^{i : 1}$ (即 $F Q_{n}^{1}$ )和 $F Q_{n}^{i : 0}$ (即 $F Q_{n}^{0}$ )。

(5) $F Q_{n}^{1}$ 和 $F Q_{n}^{0}$ 同构于 $Q_{n - 1}$ 。

3. MM*模型

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

引理3.1 [22] 一个系统 $G = (V, E)$ 是t-可诊断的，当且仅当对于每一对不同的顶点集 $(F_{1}, F_{2})$ 且 $| F_{1} |, | F_{2} | \leq t$ ， $(F_{1}, F_{2})$ 是可区分对。

4. 局部诊断度

一个图 $G = (V, E)$ ，设 $F_{1}$ 和 $F_{2}$ 是V的两个不同子集，对称差分 $F_{1} △ F_{2} = (F_{1} ∖ F_{2}) \cup (F_{2} ∖ F_{1})$ 。

引理 4.1 [1] 一个系统 $G = (V, E)$ 在顶点x处是局部t-可诊断的，如果假定测试症候 $σ_{F}$ 是由系统内存在一组包含x的故障顶点集F且 $| F | \leq t$ 生成的，那么每个故障顶点集 $F^{'}$ 要与 $σ_{F}$ 保持一致且 $| F^{'} | \leq t$ 必须包含顶点x。

引理 4.2 [5] 一个系统 $G = (V, E)$ ，如果 $x \in F_{1} △ F_{2}$ 且对于V的每一对不同的故障子集 $F_{1}$ 和 $F_{2}$ 是可区分的，其中 $| F_{1} | \leq t$ ， $| F_{2} | \leq t$ ，则点x是局部t-可诊断的。

定理 4.1 [3] [4] 一个系统 $G = (V, E)$ 在MM*模型下是t-可诊断的，当且仅当对于V的每一对不同的故障集 $F_{1}$ 和 $F_{2}$ ，其中 $| F_{1} | \leq t$ ， $| F_{2} | \leq t$ 且 $x \in F_{1} △ F_{2}$ ， $(F_{1}, F_{2})$ 满足下列条件之一：

(1) 有两个顶点 $u, w \in V (G) ∖ (F_{1} \cup F_{2})$ ，有一个顶点 $v \in F_{1} △ F_{2}$ ，使得 $u w \in E (G)$ 和 $v w \in E (G)$ 。

(2) 有两个顶点 $u, v \in F_{1} ∖ F_{2}$ ，有一个顶点 $w \in V (G) ∖ (F_{1} \cup F_{2})$ ，使得 $u w \in E (G)$ 和 $v w \in E (G)$ 。

(3) 有两个顶点 $u, v \in F_{2} ∖ F_{1}$ ，有一个顶点 $w \in V (G) ∖ (F_{1} \cup F_{2})$ ，使得 $u w \in E (G)$ 和 $v w \in E (G)$ (见图3)。

Figure 3. Illustration of a distinguishable pair $(F_{1}, F_{2})$ under the MM* model

图3. MM*模型下的可区分对 $(F_{1}, F_{2})$ 示图

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

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

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

定理 4.2 [8] 设x是一个图 $G = (V, E)$ 中的一个点。若 $d_{G} (x) \geq n$ ，我们定义一个延展星图 $E S (x; n)$ ，其中 $d_{E S (x; n)} (x) = n$ ，点集 $V (E S (x; n)) = {x} \cup {v_{i j} : i = 1, 2, \dots, n, j = 1, 2, 3, 4}$ ，边集 $E (E S (x; n)) = {(x, v_{k 1}), (v_{k 1}, v_{k 2}), (v_{k 2}, v_{k 3}), (v_{k 3}, v_{k 4}) : k = 1, 2, \dots, n}$ 。

注意x称为 $E S (x; n)$ 的根。

引理 4.6 [8] 设x是系统 $G = (V, E)$ 中的一个点且 $d_{G} (x) = n$ 。如果点x在G中存在一个延展星图 $E S (x; n)$ ，则x的局部诊断度是n。

引理 4.7 [8] 设x是图 $G = (V, E)$ 中的一个点。如果x的局部诊断度等于它在G中的度，即 $t_{l} (x) = d_{G} (x)$ ，则这个点x有强局部诊断性。

引理 4.8 [8] 设 $G = (V, E)$ 是一个图。如果G中每个点的局部诊断度都等于它在G中的度，即对于所有的 $x \in V (G)$ 都有 $t_{l} (x) = d_{G} (x)$ ，则G有强局部诊断性。

5. n维增强超立方体 $Q_{n, k}$ 的局部诊断性

引理 5.1 [18] 在n维超立方体 $Q_{n} (n \geq 6)$ 中每个顶点x处都存在一个延展星图 $E S (x; n)$ 。

引理 5.2 [18] 在n维折叠超立方体 $F Q_{n} (n \geq 6)$ 中每个顶点x处都存在一个延展星图 $E S (x; n + 1)$ 。

由增强超立方体 $Q_{n, k}$ 的性质和引理2.1，我们把证明过程分为声明一： $i \geq k$ 和声明二： $i < k$ 两个部分。

下面先证明声明一： $i \geq k$ 。

引理 5.3 对于增强超立方体 $Q_{n, k}$ 且 $n \geq 6$ 中的每一个顶点x，在顶点x处存在一个延展星图 $E S (x; n + 1)$ 。

证明我们可以沿着最后一个位置把 $Q_{n, k}$ 分解为两个不同的子图 $Q_{n, k}^{0}$ 和 $Q_{n, k}^{1}$ ，在子图中每个顶点 $x = u_{1} u_{2} \dots u_{n} \in V (Q_{n, k}^{j}) (j \in {0, 1})$ 在最后一个位置 $u_{n}$ 处都有一个固定的整数 $j (j \in {0, 1})$ 。显然， $Q_{n, k}^{j}$ 同构于 $Q_{n - 1}$ ，且 $Q_{n - 1}$ 是一个 $n - 1$ 维超立方体。我们需要在顶点x处找到一个延展星图 $E S (x; n - 1)$ 作为 $Q_{n, k}$ 的子图。由引理5.1，在n维超立方体 $Q_{n} (n \geq 6)$ 中每个顶点x处都存在一个延展星图 $E S (x; n)$ 。因此在 $Q_{n, k}^{j}$ 中顶点x处存在一个延展星图 $E S (x; n - 1)$ 。由引理2.5， $Q_{n, k}$ 是点传递的。因此，顶点 $x = u_{1} u_{2} \dots u_{k} u_{k + 1} \dots u_{n} \in V (Q_{n, k}^{j})$ 可以作为延展星图 $E S (x; n - 1)$ 的根。由引理2.5，子图 $Q_{n, k}^{j}$ 中每个顶点都存在两个外部邻点。设顶点x的两个外部邻点分别是 $y_{0} = u_{1} u_{2} \dots u_{k} u_{k + 1} \dots u_{n - 1} {\bar{u}}_{n}$ 和 $y_{1} = u_{1} u_{2} \dots u_{k - 1} {\bar{u}}_{k} \dots {\bar{u}}_{n - 1} {\bar{u}}_{n}$ 。注意有两条不同的3长路

$P_{1} = 〈 u_{1} u_{2} \dots u_{k} u_{k + 1} \dots u_{n - 1} {\bar{u}}_{n}, u_{1} \dots u_{n - 2} {\bar{u}}_{n - 1} {\bar{u}}_{n}, u_{1} \dots u_{n - 3} {\bar{u}}_{n - 2} {\bar{u}}_{n - 1} {\bar{u}}_{n}, u_{1} \dots u_{n - 4} {\bar{u}}_{n - 3} {\bar{u}}_{n - 2} {\bar{u}}_{n - 1} {\bar{u}}_{n} 〉$ ;

$\begin{array}{l} P_{2} = 〈 u_{1} \dots u_{k - 1} {\bar{u}}_{k} \dots {\bar{u}}_{n - 1} {\bar{u}}_{n}, u_{1} \dots u_{k - 1} {\bar{u}}_{k} {\bar{u}}_{k + 1} \dots {\bar{u}}_{n - 2} u_{n - 1} {\bar{u}}_{n}, u_{1} u_{2} \dots {\bar{u}}_{k} {\bar{u}}_{k + 1} \dots {\bar{u}}_{n - 3} u_{n - 2} u_{n - 1} {\bar{u}}_{n}, \\ u_{1} u_{2} \dots {\bar{u}}_{k} {\bar{u}}_{k + 1} \dots {\bar{u}}_{n - 4} u_{n - 3} u_{n - 2} u_{n - 1} {\bar{u}}_{n} 〉 \end{array}$

我们连接 $P_{1}$ 和 $P_{2}$ 到x，然后把它与 $E S (x; n - 1)$ 结合。这样，我们就在 $Q_{n, k}$ 中顶点x处找到一个延展星图 $E S (x; n + 1)$ 。

定理 5.1 设 $Q_{n, k}$ 是增强超立方体且 $n \geq 6$ ，则 $Q_{n, k}$ 的诊断度是 $n + 1$ ，即 $t (Q_{n, k}) = n + 1$ ， $Q_{n, k}$ 有强局部诊断性。

证明由引理4.6和5.3， $Q_{n, k}$ 中每个顶点x的局部可诊断性是 $n + 1$ 。由引理4.5， $Q_{n, k}$ 的局部诊断性是 $n + 1$ ，即 $t (Q_{n, k}) = n + 1$ 。由于 $Q_{n, k}$ 中每个顶点x的度是 $n + 1$ ，每个顶点的局部可诊断性等于它的度，由引理5.1， $Q_{n, k}$ 有强局部可诊断性。

引理 5.4 设 $F_{e}$ 是任意缺失边集且 $| F_{e} | \leq n - 1$ 。对于 $Q_{n, k} (n \geq 6)$ 中每一个顶点x，在 $Q_{n, k} - F_{e}$ 中的x处存在一个延展星图 $E S (x; d_{Q_{n, k} - F_{e}} (x))$ 。

证明由引理2.5， $Q_{n, k}$ 是点传递的。因此， $x = u_{1} \dots u_{k} \dots u_{n - 1} 0 (x \in V (Q_{n, k}^{0}))$ 可以被作为延展星图 $E S (x; d_{Q_{n, k} - F_{e}} (x))$ 的一个根。增强超立方体 $Q_{n, k} (1 \leq k \leq n - 1)$ 可以被分解为两个不同的子图 $Q_{n, k}^{0}$ 和 $Q_{n, k}^{1}$ ，其中每个子图的顶点 $x = u_{1} u_{2} \dots u_{n} \in V (Q_{n, k}^{j}) (j \in {0, 1})$ 在最后一位 $u_{n}$ 处都有一个固定整数j。显然 $Q_{n, k}^{j}$ 同构于 $Q_{n - 1}$ ， $Q_{n - 1}$ 是一个 $n - 1$ 维的超立方体。设 $F_{j} = F \cap E (Q_{n, k}^{j})$ 对于 $j \in {1, 0}$ ， $| F_{0} | = \max {| F_{0} |, | F_{1} |}$ 。由 $Q_{n, k}$ 的定义， $Q_{n, k}^{j}$ 同构于 $Q_{n - 1}$ 且 $Q_{n, k}^{j}$ 中的每个顶点在另外一个子图中有两个外部邻域。设x在 $Q_{n, k}^{0}$ 中，那么 $y_{0} = u_{1} u_{2} \dots u_{k} u_{k + 1} \dots u_{n - 1} {\bar{u}}_{n} \in V (Q_{n, k}^{1})$ 和 $y_{1} = u_{1} u_{2} \dots {\bar{u}}_{k} {\bar{u}}_{k + 1} \dots {\bar{u}}_{n - 1} {\bar{u}}_{n} \in V (Q_{n, k}^{1})$ 是x的邻域。为了证明这个引理，我们首先需要在 $Q_{n, k}^{0} - F_{0}$ 中顶点x处找到一个延展星图 $E S (x; d_{Q_{n, k}^{0} - F_{0}} (x))$ 。然后找到两条不同的3长路 $P_{y_{0}}$ 和 $P_{y_{1}}$ ，而且都在 $Q_{n, k}^{1}$ 中。我们连接 $P_{y_{0}}$ 和 $P_{y_{1}}$ 到x，把它结合到 $E S (x; d_{Q_{n, k}^{0} - F_{0}} (x))$ 。那么，我们可以在 $Q_{n, k} - F_{e}$

中顶点x处找到一个延展星图 $E S (x; d_{Q_{n, k} - F_{e}} (x))$ 。考虑下面三种情形。

情形 1 $| F_{0} | \leq n - 3$ 。

注意到 $Q_{n, k}^{0}$ 同构于 $Q_{n - 1}$ 且 $| F_{0} | \leq n - 3$ 。由引理2.7，设 $F_{e}$ 是一个任意缺失边集且 $| F_{e} | \leq n - 3$ ，对于 $Q_{n - 1}$ 中每一个顶点x，在 $Q_{n - 1} - F_{e}$ 中顶点x处都可以找到一个延展星图 $E S (x; d_{Q_{n - 1} - F_{e}} (x))$ 。那么我们可以在 $Q_{n, k}^{0} - F_{0}$ 中顶点x处找到一个延展星图 $E S (x; d_{Q_{n, k}^{0} - F_{0}} (x))$ 。假设 $A = E S (x; d_{Q_{n, k}^{0} - F_{0}} (x))$ 。如果 $x y_{0} \in F_{e}$ ， $x y_{1} \in F_{e}$ ，那么我们不需要去找到 $P_{y_{0}}$ 、 $P_{y_{1}}$ 。如果 $x y_{0}$ 和 $x y_{1}$ 中只有一条边属于 $F_{e}$ ，则不妨假设 $x y_{0} \in F_{e}$ 。我们需要在 $Q_{n, k}^{1} - F_{1}$ 中找到一条从 $y_{1}$ 开始的3长路 $P_{y_{1}}$ 并且把它连接到A。由引理2.5， $κ (Q_{n, k}^{1}) = κ (Q_{n - 1}) = n - 1 > n - 3 > | F_{1} |$ 。因此， $Q_{n, k}^{1} - F_{1}$ 是连通的。当 $n \geq 6$ 时， $| V (Q_{n, k}^{1}) | = | V (Q_{n - 1}) | = 2^{n - 1} \geq 2^{5} = 32$ 。因此在 $Q_{n, k}^{1} - F_{1}$ 中存在一条从 $y_{0}$ 开始的3长路 $P_{y_{0}}$ 并且把 $P_{y_{0}}$ 连接到

x，再与A结合。最后我们在 $Q_{n, k} - F_{e}$ 中顶点x处找到一个延展星图 $E S (x; d_{Q_{n, k} - F_{e}} (x))$ 。如果 $x y_{0} \notin F_{e}$ 、 $x y_{1} \notin F_{e}$ ，我们需要分别找到两条不同的路径3长路 $P_{y_{0}}$ 和 $P_{y_{1}}$ 。设 $H_{j} (j \in {0, 1})$ 是由第 $n - 1$ 位是j、第1位是0的点集导出的 $Q_{n, k}^{1}$ 的子图。由 $Q_{n, k}$ 的定义， $H_{j}$ 同构于 $Q_{n - 2}$ 。由引理2.5， $κ (H_{j}) = κ (Q_{n - 2}) = n - 2 > | F_{1} |$ ，那么 $H_{j} - F_{1}$ 是连通的。当 $n \geq 6$ 时， $| V (H_{j}) | = | V (Q_{n - 2}) | = 2^{n - 2} \geq 2^{4} = 16$ 。所以，在 $H_{j} - F_{1}$ 中存在两条不同的3长路 $P_{y_{0}}$ 和 $P_{y_{1}}$ ，然后连接 $P_{y_{0}}$ 和 $P_{y_{1}}$ 到x。最后我们可以在 $Q_{n, k} - F_{e}$ 中顶点x处找到一个延展星图 $E S (x; d_{Q_{n, k} - F_{e}} (x))$ 。

情形 2 $| F_{0} | = n - 2$ 。

注意到 $y_{0} = u_{1} u_{2} \dots u_{k} u_{k + 1} \dots u_{n - 1} {\bar{u}}_{n}$ 和 $y_{1} = u_{1} u_{2} \dots {\bar{u}}_{k} {\bar{u}}_{k + 1} \dots {\bar{u}}_{n - 1} {\bar{u}}_{n}$ 。那么 $y_{0} \in V (Q_{n, k}^{1})$ ， $y_{1} \in V (Q_{n, k}^{1})$ ，即 $y_{0} = u_{1} u_{2} \dots u_{k} u_{k + 1} \dots u_{n - 1} 1$ ， $y_{1} = u_{1} u_{2} \dots u_{k - 1} {\bar{u}}_{k} {\bar{u}}_{k + 1} \dots {\bar{u}}_{n - 1} 1$ 。我们可以分别找到从 $y_{0}$ 、 $y_{1}$ 开始的两条不同3长路，

$P_{y_{0}}^{1} = 〈 u_{1} u_{2} \dots u_{k} u_{k + 1} \dots u_{n - 1} 1, u_{1} u_{2} \dots u_{n - 3} {\bar{u}}_{n - 2} u_{n - 1} 1, u_{1} \dots u_{n - 4} {\bar{u}}_{n - 3} {\bar{u}}_{n - 2} u_{n - 1} 1, u_{1} \dots u_{n - 5} {\bar{u}}_{n - 4} {\bar{u}}_{n - 3} {\bar{u}}_{n - 2} u_{n - 1} 1 〉$ ;

$P_{y_{0}}^{2} = 〈 u_{1} u_{2} \dots u_{k} u_{k + 1} \dots u_{n - 1} 1, u_{1} {\bar{u}}_{2} u_{3} \dots u_{k} u_{k + 1} \dots u_{n - 1} 1, u_{1} {\bar{u}}_{2} {\bar{u}}_{3} u_{4} \dots u_{k} u_{k + 1} \dots u_{n - 1} 1, u_{1} {\bar{u}}_{2} {\bar{u}}_{3} {\bar{u}}_{4} u_{5} \dots u_{k} u_{k + 1} \dots u_{n - 1} 1 〉$ ;

$\begin{array}{l} P_{y_{1}}^{1} = 〈 u_{1} u_{2} \dots u_{k - 1} {\bar{u}}_{k} {\bar{u}}_{k + 1} \dots {\bar{u}}_{n - 1} 1, u_{1} u_{2} \dots u_{k - 1} {\bar{u}}_{k} \dots {\bar{u}}_{n - 3} u_{n - 2} {\bar{u}}_{n - 1} 1, u_{1} \dots u_{k - 1} {\bar{u}}_{k} \dots {\bar{u}}_{n - 4} u_{n - 3} u_{n - 2} {\bar{u}}_{n - 1} 1, \\ u_{1} \dots u_{k - 1} {\bar{u}}_{k} \dots {\bar{u}}_{n - 5} u_{n - 4} u_{n - 3} u_{n - 2} {\bar{u}}_{n - 1} 1 〉 \end{array}$ ;

$P_{y_{1}}^{2} = 〈 u_{1} u_{2} \dots u_{k - 1} {\bar{u}}_{k} {\bar{u}}_{k + 1} \dots {\bar{u}}_{n - 1} 1, u_{1} {\bar{u}}_{2} u_{3} \dots u_{k - 1} {\bar{u}}_{k} \dots {\bar{u}}_{n - 1} 1, u_{1} {\bar{u}}_{2} {\bar{u}}_{3} u_{4} \dots u_{k - 1} {\bar{u}}_{k} \dots {\bar{u}}_{n - 1} 1, u_{1} {\bar{u}}_{2} {\bar{u}}_{3} {\bar{u}}_{4} u_{5} \dots u_{k - 1} {\bar{u}}_{k} \dots {\bar{u}}_{n - 1} 1 〉$ .

$P_{y_{0}}^{1}, P_{y_{0}}^{2}, P_{y_{1}}^{1}$ 和 $P_{y_{1}}^{2}$ 都在 $Q_{n, k}^{1}$ 中。显然， $P_{y_{0}}^{1}, P_{y_{0}}^{2}, P_{y_{1}}^{1}$ 和 $P_{y_{1}}^{2}$ 除了 $y_{0}$ 和 $y_{1}$ 之外没有公共顶点。因为 $| F | \leq n - 1$ 且 $| F_{0} | = n - 2$ ，那么在 $Q_{n, k}^{0}$ 外部最多存在一条缺失边F，即 $| F_{1} | \leq 1$ 。因此，我们可以从 $P_{y_{0}}^{1}$ 和 $P_{y_{0}}^{2}$ 中选择 $P_{y_{0}}^{1}$ 作为一条不包含缺失边的3长路。 $P_{y_{1}}$ 类似。设f是 $F_{0}$ 中的一个任意元素(即 $f \in F_{0}$ )，让 $F^{'} = F_{0} ∖ {f}$ 。那么 $| F^{'} | = n - 3$ ，由归纳假设，在 $Q_{n, k}^{0} - F^{'}$ 中存在一个延展星图 $E S (x; d_{Q_{n, k}^{0} - F^{'}} (x))$ 。设 $A = E S (x; d_{Q_{n, k}^{0} - F^{'}} (x))$ 。如果A不包含f，那么我们可以在 $Q_{n, k}^{0} - F_{0}$ 中顶点x处找到一个延展星图 $E S (x; d_{Q_{n, k}^{0} - F_{0}} (x)) = A$ 。现在我们讨论A包含f。

情形 2.1 f与x相关联。

我们可以通过删除包含f的这条路找到一个延展星图 $E S (x; d_{Q_{n, k}^{0} - F_{0}} (x))$ 。然后连接 $P_{y_{0}}$ 到x，与 $E S (x; d_{Q_{n, k}^{0} - F_{0}} (x))$ 结合。因此，我们在 $Q_{n, k} - F_{e}$ 中点x处可以找到一个延展星图。

情形 2.2 f与x不相关联。

令 $P_{u}$ 是一条从u开始的3长路并且它包含f，然后u与x相关联。注意 $u \in V (Q_{n, k}^{0})$ 。由引理2.5，不失一般性，令 $u = {\bar{u}}_{1} u_{2} \dots u_{n - 1} 0$ ，u有两个外部邻域 $u_{0} = {\bar{u}}_{1} u_{2} \dots u_{k} u_{k + 1} \dots u_{n - 1} 1 \in V (Q_{n, k}^{1})$ 和 $u_{1} = {\bar{u}}_{1} u_{2} \dots {\bar{u}}_{k} {\bar{u}}_{k + 1} \dots {\bar{u}}_{n - 1} 1 \in V (Q_{n, k}^{1})$ 。因为 $| F_{e} | \leq n - 1$ ， $| F_{0} | = n - 2$ ，在 $Q_{n, k}^{0}$ 外面至多存在 $F_{e}$ 中的一条边，我们取u的一个外部邻域 $u_{0}$ 且 $u u_{0} \notin F_{e}$ 。设 $H_{i j} (i \in {u_{1}, {\bar{u}}_{1}}, j \in {u_{n - 1}, {\bar{u}}_{n - 1}})$ 是由第1位是i、第 $n - 1$ 位是j、第n位是1的点集导出的 $Q_{n, k}^{1}$ 的子图。由 $Q_{n, k}$ 的定义， $H_{i j}$ 同构于 $Q_{n - 3}$ 。 $Q_{n, k}^{1}$ 可以被分解为四个不同的子图 $H_{{\bar{u}}_{1}, u_{n - 1}}, H_{{\bar{u}}_{1}, {\bar{u}}_{n - 1}}, H_{u_{1}, u_{n - 1}}, H_{u_{1}, {\bar{u}}_{n - 1}}$ 。由此可知， $u_{0} \in V (H_{{\bar{u}}_{1}, u_{n - 1}})$ ， $u_{1} \in V (H_{{\bar{u}}_{1}, {\bar{u}}_{n - 1}})$ ， $y_{0} \in V (H_{u_{1}, u_{n - 1}})$ ， $y_{1} \in V (H_{u_{1}, {\bar{u}}_{n - 1}})$ 。由引理2.5， $κ (H_{i j}) = κ (Q_{n - 3}) = n - 3 > | F_{1} |$ ，我们可以得到 $H_{i j} - F_{1}$ 是连通的。当 $n \geq 6$ 时， $| V (H_{i j}) | = | V (Q_{n - 3}) | = 2^{n - 3} \geq 2^{3} = 8$ 。因此我们在 $H_{{\bar{u}}_{1}, u_{n - 1}} - F_{1}$ 中找到3长路 $P_{y_{0}}$ ，在 $H_{{\bar{u}}_{1}, {\bar{u}}_{n - 1}} - F_{1}$ 中找到3长路 $P_{y_{1}}$ ，在 $H_{u_{1}, u_{n - 1}} - F_{1}$ 中找到2长路 $P_{u_{0}}$ ，在 $H_{u_{1}, {\bar{u}}_{n - 1}} - F_{1}$ 找到2长路 $P_{u_{1}}$ 。显然，这四条路没有公共顶点。我们连接 $P_{y_{0}}$ 到x， $P_{y_{1}}$ 到x， $P_{u_{0}}$ 到u，然后把它与 $E S (x; d_{Q_{n, k}^{0} - F_{0}} (x))$ 结合。那么，我们可以在 $Q_{n, k} - F_{e}$ 中顶点x处找到一个延展星图 $E S (x; d_{Q_{n, k} - F_{e}} (x))$ 。 $u u_{1} \notin F_{e}$ 的讨论与上述类似。

情形 3 $| F_{0} | = n - 1$ 。

设 $f, f^{'}$ 是 $F_{0}$ 中任意元素， $F^{'} = F_{0} \ {f, f^{'}}$ 。那么 $| F^{'} | = n - 3$ 。由归纳假设，我们可以在 $Q_{n, k}^{0} - F^{'}$ 中得到一个延展星图 $E S (x; d_{Q_{n, k}^{0} - F^{'}} (x))$ 。令 $A = E S (x; d_{Q_{n, k}^{0} - F^{'}} (x))$ 。

情形 3.1A不包含f和 $f^{'}$ 。

我们可以发现这个延展星图 $E S (x; d_{Q_{n, k}^{0} - F_{0}} (x)) = A$ 。注意 $| F_{e} | \leq n - 1$ ， $| F_{0} | = n - 1$ 。那么在 $Q_{n, k}^{1}$ 中不存在缺失边 $F_{e}$ 。因此我们可以找到两条不同的3长路 $P_{y_{0}}$ 和 $P_{y_{1}}$ ，然后我们连接 $P_{y_{0}}$ 和 $P_{y_{1}}$ 到x。因此，我们在 $Q_{n, k} - F_{e}$ 中得到一个延展星图 $E S (x; d_{Q_{n, k} - F_{e}} (x))$ 。

情形 3.2A包含f或 $f^{'}$ 中的一条。

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

情形 3.3A包含f和 $f^{'}$ 。

如果f和 $f^{'}$ 都与x相关联，我们可以通过删除这两条分别包含f和 $f^{'}$ 的边得到延展星图 $E S (x; d_{Q_{n, k}^{0} - F_{0}} (x))$ 。后面的证明完全类似于情形3.1。如果 ${f, f^{'}}$ 中只有一条边与x相关联，不失一般性，令 $f^{'}$ 与x相关联、f不与x相关联。我们可以在 $Q_{n, k}^{0} - {F_{0} \cup f^{'}}$ 中找到一个延展星图 $E S (x; d_{Q_{n, k}^{0} - {F_{0} \cup f^{'}}} (x))$ 。证明类似于情形2.2。如果f和 $f^{'}$ 都不与x相关联，我们考虑f和 $f^{'}$ 是否属于一条路。如果f和 $f^{'}$ 都属于同一条路，那么后面的证明类似于情形2.2。因此我们假设f和 $f^{'}$ 属于A中不同的两条路。设 $P_{u}$ 是一条从 $u (u = {\bar{u}}_{1} u_{2} \dots u_{n - 1} 0)$ 开始的3长路并且包含f。设 $P_{v}$ 是一条从 $v (v = {\bar{u}}_{1} {\bar{u}}_{2} \dots {\bar{u}}_{n - 1} 0)$ 开始的3长路并且包含 $f^{'}$ 。u和v在 $Q_{n, k}^{1}$ 中分别有两个外部邻域，设u和v的一个外部邻域分别是 $u_{0}$ 和 $v_{0}$ ， $u_{0}, v_{0} \in V (Q_{n, k}^{1})$ 。注意到 $| F_{e} | \leq n - 1$ ， $| F_{0} | = n - 1$ ，那么在 $Q_{n, k}^{0}$ 外部不存在 $F_{e}$ 中的任何边。设 $H_{i j} (i \in {u_{1}, {\bar{u}}_{1}}, j \in {u_{n - 1}, {\bar{u}}_{n - 1}})$ 是由第1位是i、第 $n - 1$ 位是j、第n位是1的点集导出的 $Q_{n, k}^{1}$ 的子图。由 $Q_{n, k}$ 的定义， $H_{i j}$ 同构于 $Q_{n - 3}$ 。 $Q_{n, k}^{1}$ 可以被分解为四个不同的子图 $H_{{\bar{u}}_{1}, u_{n - 1}}, H_{{\bar{u}}_{1}, {\bar{u}}_{n - 1}}, H_{u_{1}, u_{n - 1}}, H_{u_{1}, {\bar{u}}_{n - 1}}$ 。因此， $v_{0} \in V (H_{{\bar{u}}_{1}, {\bar{u}}_{n - 1}})$ ，由引理2.5， $κ (H_{i j}) = κ (Q_{n - 3}) = n - 3 > | F_{1} |$ ， $H_{i j} - F_{1}$ 是连通的。我们可以在 $Q_{n, k}^{1}$ 中分别找到一条从 $u_{0}$ 、 $v_{0}$ 开始的3长路。最后我们在 $Q_{n, k} - F_{e}$ 中顶点x处得到一个延展星图 $E S (x; d_{Q_{n, k} - F_{e}} (x))$ 。

定理 5.2令 $Q_{n, k} (n \geq 6)$ ，设 $F_{e}$ 是任意缺失边集且 $| F_{e} | \leq n - 1$ 。对于 $Q_{n, k}$ 中每个顶点x， $Q_{n, k} - F_{e}$ 有强局部可诊断性。

证明由引理4.6和5.4，对于 $n \geq 6$ 且 $| F_{e} | \leq n - 1$ ， $Q_{n, k} - F_{e}$ 的每一个顶点x的局部可诊断度等于它剩余的度。由引理4.8，在 $Q_{n, k} - F_{e}$ 中的每个顶点x有强局部可诊断性。由引理5.1， $Q_{n, k} - F_{e}$ 有强局部可诊断性。

现在我们证明声明二： $i < k$ (即 $1 \leq i < k \leq n - 1$ )。

由引理2.1，增强超立方体 $Q_{n, k} (1 \leq k \leq n - 1)$ 可以被分解为两个子图 $Q_{n, k}^{0}$ 和 $Q_{n, k}^{1}$ ，它们是两个 $n - 1$ 维增强超立方体。由引理2.3， $Q_{n, k}^{0}$ 和 $Q_{n, k}^{1}$ 同构于 $Q_{n - 1, k - 1}$ 。首先，我们讨论 $Q_{n, 2}$ 。

引理 5.5对于增强超立方体 $Q_{n, 2}$ 且 $n \geq 6$ 中的每一个顶点x，在顶点x处存在一个延展星图 $E S (x; n + 1)$ 。

证明我们可以沿着第一个位置把 $Q_{n, 2}$ 分解为两个不同的子图 $Q_{n, 2}^{0}$ 和 $Q_{n, 2}^{1}$ ，在子图中每个顶点 $x = u_{1} u_{2} \dots u_{n} \in V (Q_{n, 2}^{j}) (j \in {0, 1})$ 在第一个位置 $u_{1}$ 处都有一个固定的整数 $j (j \in {0, 1})$ 。显然， $Q_{n, 2}^{j}$ 同构于 $Q_{n - 1, 1}$ ，且 $Q_{n - 1, 1}$ 是一个 $n - 1$ 维增强超立方体。由引理2.2， $Q_{n - 1, 1}$ 是折叠超立方体 $F Q_{n - 1}$ 。

我们应该在顶点x处找到一个延展星图作为 $Q_{n, 2}$ 的子图。由引理2.5， $Q_{n, 2}$ 是点传递的。因此，顶点 $x = 00 \dots 00 \in V (Q_{n, 2}^{0})$ 可以作为延展星图 $E S (x; n)$ 的根。由引理5.2，在n维折叠超立方体 $F Q_{n} (n \geq 6)$ 中每个顶点x处都存在一个延展星图 $E S (x; n + 1)$ 。因此在 $Q_{n, 2}^{0}$ 中顶点x处存在一个延展星图 $E S (x; n)$ 。注意顶点x存在一个外部邻点 $y = 100 \dots 00 \in V (Q_{n, 2}^{1})$ 。注意到3长路 $P_{y} = 〈 100 \dots 00, 110 \dots 00, 1110 \dots 00, 11110 \dots 00 〉$ 在 $Q_{n, 2}^{1}$ 中。我们连接 $P_{y}$ 到x，然后与 $E S (x; n)$ 结合。因此，我们在 $Q_{n, 2}$ 中点x处得到一个延展星图 $E S (x; n + 1)$ 。

定理 5.3设 $Q_{n, 2}$ 是增强超立方体且 $n \geq 6$ ，则 $Q_{n, 2}$ 的诊断度是 $n + 1$ ，即 $t (Q_{n, 2}) = n + 1$ ， $Q_{n, 2}$ 有强局部诊断性。

证明由引理4.6 和5.5， $Q_{n, 2}$ 每个顶点x的局部可诊断度是 $n + 1$ 。由引理 4.5， $Q_{n, 2}$ 的局部可诊断度是 $n + 1$ ，即 $t (Q_{n, 2}) = n + 1$ 。由于 $Q_{n, 2}$ 中每个顶点x的度是 $n + 1$ ，每个顶点的局部可诊断度等于它的度，由引理5.1， $Q_{n, 2}$ 有强局部可诊断性。

引理 5.6设 $F_{e}$ 是任意缺失边集且 $| F_{e} | \leq n - 1$ 。对于 $Q_{n, 2} (n \geq 6)$ 中每一个顶点x，在 $Q_{n, 2} - F_{e}$ 中的x处存在一个延展星图 $E S (x; d_{Q_{n, 2} - F_{e}} (x))$ 。

证明由引理2.5， $Q_{n, 2}$ 是点传递的。因此， $x = 00 \dots 00 \in V (Q_{n, 2}^{0})$ 可以被作为延展星图 $E S (x; d_{Q_{n, 2} - F_{e}} (x))$ 的一个根。增强超立方体 $Q_{n, 2}$ 可以被分解为两个不同的子图 $Q_{n, 2}^{0}$ 和 $Q_{n, 2}^{1}$ ，其中每个子图的顶点 $x = u_{1} u_{2} \dots u_{n} \in V (Q_{n, 2}^{j}) (j \in {0, 1})$ 在第一位 $u_{1}$ 处都有一个固定整数j。显然 $Q_{n, 2}^{j}$ 同构于 $Q_{n - 1, 1}$ ， $Q_{n - 1, 1}$ 是一个 $n - 1$ 维的增强超立方体。由引理 2.2， $Q_{n - 1, 1}$ 是折叠超立方体 $F Q_{n - 1}$ 。设 $F_{j} = F \cap E (Q_{n, 2}^{j})$ 对于 $j \in {1, 0}$ ， $| F_{0} | = \max {| F_{0} |, | F_{1} |}$ 。由 $Q_{n, k}$ 的定义， $Q_{n, 2}^{j}$ 同构于 $Q_{n - 1}$ 且 $Q_{n, 2}^{j}$ 中的每个顶点在另外一个子图有一个外部邻域。设x在 $Q_{n, 2}^{0}$ 中，那么 $y = 100 \dots 00$ 且 $y \in V (Q_{n, 2}^{1})$ 是x的邻域。为了证明这个引理，我们首先需要在 $Q_{n, 2}^{0} - F_{0}$ 中顶点x处找到一个延展星图 $E S (x; d_{Q_{n, 2}^{0} - F_{0}} (x))$ 。然后找到一条3长路 $P_{y}$ ，并且在 $Q_{n, 2}^{1}$ 中。我们连接 $P_{y}$ 到x，把它结合到 $E S (x; d_{Q_{n, 2}^{0} - F_{0}} (x))$ 。故我们可以在 $Q_{n, 2} - F_{e}$ 中顶点x处找到一个延展星图 $E S (x; d_{Q_{n, 2} - F_{e}} (x))$ 。考虑下面两种情形。

情形 1 $| F_{0} | \leq n - 2$ 。

注意到 $Q_{n, 2}^{0}$ 同构于 $F Q_{n - 1}$ ， $| F_{0} | \leq n - 2$ 。由引理2.6，令 $F_{e}$ 是一个任意缺失边集且 $| F_{e} | \leq n - 2$ ，对于 $F Q_{n - 1}$ 中每一个顶点x，在 $F Q_{n - 1} - F_{e}$ 中都可以找到一个延展星图 $E S (x; d_{F Q_{n - 1} - F_{e}} (x))$ 。那么我们可以在 $Q_{n, 2}^{0} - F_{0}$ 中顶点x处找到一个延展星图 $E S (x; d_{Q_{n, 2}^{0} - F_{0}} (x))$ 。设 $A = E S (x; d_{Q_{n, 2}^{0} - F_{0}} (x))$ 。如果 $x y \in F_{e}$ ，那么我们不需要通过 $x y$ 来扩展A。假设 $x y \notin F_{e}$ 。由引理2.5， $κ (Q_{n, 2}^{1}) = κ (F Q_{n - 1}) = n > n - 2 > | F_{1} |$ ，那么 $Q_{n, 2}^{1} - F_{1}$ 是连通的。当 $n \geq 6$ 时， $| V (Q_{n, 2}^{1}) | = | V (F Q_{n - 1}) | = 2^{n - 1} \geq 2^{5} = 32$ 。因此在 $Q_{n, 2}^{1} - F_{1}$ 中存在一条从y开始的3长路 $P_{y} = 〈 100 \dots 00, 110 \dots 00, 1110 \dots 00, 11110 \dots 00 〉$ ，把它连接到A，那么我们可以在 $Q_{n, 2} - F_{e}$ 中x处找到一个延展星图 $E S (x; d_{Q_{n, 2} - F_{e}} (x))$ 。

情形 2 $| F_{0} | = n - 1$ 。

令f是 $F_{0}$ 的任意一个元素(即 $f \in F_{0}$ )且 $F^{'} = F_{0} ∖ {f}$ 。那么 $| F^{'} | = n - 2$ 。由归纳假设，我们可以在 $Q_{n, 2}^{0} - F^{'}$ 中得到一个延展星图 $E S (x; d_{Q_{n, 2}^{0} - F^{'}} (x))$ 。令 $A = E S (x; d_{Q_{n, 2}^{0} - F^{'}} (x))$ 。

情形 2.1A不包含f。

我们可以找到一个延展星图 $E S (x; d_{Q_{n, 2}^{0} - F_{0}} (x)) = A$ 。注意到 $| F_{e} | \leq n - 1$ ， $| F_{0} | = n - 1$ ，那么在 $Q_{n, 2}^{1}$ 中不存在 $F_{e}$ 中的任何缺失边。因此在 $Q_{n, 2}^{1} - F_{1}$ 中存在一条从y开始的3长路 $P_{y}$ ，通过 $x y$ 连接到A，在 $Q_{n, 2} - F_{e}$ 中x处得到一个延展星图 $E S (x; d_{Q_{n, 2} - F_{e}} (x))$ 。

情形 2.2A包含f。

如果f与x相关联，我们可以通过删除这条包含f的路得到延展星图 $E S (x; d_{Q_{n, 2}^{0} - F_{e}} (x))$ 。后面的证明完全类似于情形2.1。如果f不与x相关联，令 $P_{u}$ 是一条从u开始的3长路并且包含f，u在 $Q_{n, 2}^{1}$ 有一个邻域 $u_{0}$ 。由 $Q_{n, k}$ 的定义， $N_{Q_{n, 2}^{0}} (x) = {0100 \dots 00, 0010 \dots 00, \dots, 00 \dots 01, 011 \dots 11}$ 。不失一般性，令 $u = 010 \dots 00$ ，则 $u_{0} = 110 \dots 00$ 。我们需要在 $Q_{n, 2}^{1}$ 找到一条不包含缺失边的3长路 $P_{u_{0}}$ 。设 $H_{j} (j \in {0, 1})$ 是由第1位是1、第2位是j的点集导出的 $Q_{n, 2}^{1}$ 的子图。由增强超立方体 $Q_{n, k}$ 的定义， $H_{j}$ 同构于 $Q_{n - 2}$ 。 $Q_{n, 2}^{1}$ 可以被分解为两个不同的子图 $H_{0}, H_{1}$ ，且 $u_{0} \in V (H_{1})$ ， $y \in V (H_{0})$ 。显然， $P_{y}$ 和 $P_{u_{0}}$ 之间没有公共点。由引理2.5， $κ (H_{j}) = κ (Q_{n - 2}) = n - 2 > | F_{1} |$ ，故 $H_{j} - F_{1}$ 是连通的。当 $n \geq 6$ 时， $| V (H_{j}) | = | V (Q_{n - 2}) | = 2^{n - 2} \geq 2^{4} = 16$ ，因此我们可以在 $H_{0} - F_{1}$ 和 $H_{1} - F_{1}$ 中分别找到一条3长路 $P_{y}$ 和一条2长路 $P_{u_{0}}$ 。显然，这两条路是点不交的。因此我们在 $Q_{n, 2} - F_{e}$ 中x点处得到了一个延展星图 $E S (x; d_{Q_{n, 2} - F_{e}} (x))$ 。

定理 5.4令 $Q_{n, 2} (n \geq 6)$ ，设 $F_{e}$ 是任意缺失边集且 $| F_{e} | \leq n - 1$ 。对于 $Q_{n, 2}$ 中每个顶点x， $Q_{n, 2} - F_{e}$ 有强局部可诊断性。

证明由引理4.6 和5.6， $Q_{n, 2} - F_{e}$ 的每一个顶点x的局部诊断度等于它剩余的度对于 $n \geq 6$ 且 $| F_{e} | \leq n - 1$ 。由引理4.8，在 $Q_{n, 2} - F_{e}$ 中的每个顶点x有强局部诊断性。由引理 5.2， $Q_{n, 2} - F_{e}$ 有强局部诊断性。

根据上述证明，对于 $Q_{n, 2} (n \geq 6)$ 中的每个顶点x且 $| F_{e} | \leq n - 1$ ，我们可以在 $Q_{n, 2} - F_{e}$ 中顶点x处找到一个延展星图 $E S (x; d_{Q_{n, 2} - F_{e}} (x))$ 。由引理2.1，增强超立方体 $Q_{n, 3}$ 可以被分解为两个子图 $Q_{n, 3}^{0}$ 和 $Q_{n, 3}^{1}$ ，其中

的每个点 $x = u_{1} u_{2} \dots u_{n} \in V (Q_{n, 3}^{j}) (j \in {0, 1})$ 在第一位 $u_{1}$ 处有一个固定整数j。显然， $Q_{n, 3}^{j}$ 同构于 $Q_{n - 1, 2}$ 且 $Q_{n - 1, 2}$ 是 $n - 1$ 维的增强超立方体。由于 $Q_{n, 2}$ 和 $Q_{n, 2} - F_{e}$ 具有强局部可诊断性，利用相同的证明方法得到 $Q_{n, 3}$ 有强局部可诊断性。设 $F_{e}$ 是任意缺失边集且 $| F_{e} | \leq n - 1$ 。对于 $Q_{n, 3}$ 中每个顶点x， $Q_{n, 3} - F_{e}$ 有强局部可诊断性。再利用相同的证明方法，我们使用 $Q_{n, 3}$ 和 $Q_{n, 3} - F_{e}$ 的结果可以证明出 $Q_{n, 4}$ 和 $Q_{n, 4} - F_{e}$ 也具有强局部诊断性。以此类推， $Q_{n, n - 1}$ 具有强的局部可诊断性。设 $F_{e}$ 是任意缺失边集且 $| F_{e} | \leq n - 1$ 。对于 $Q_{n, n - 1}$ 中每个顶点x， $Q_{n, n - 1} - F_{e}$ 有强局部诊断性。最后，我们可以得到对于 $1 \leq i < k \leq n - 1$ ， $Q_{n, k}$ 和 $Q_{n, k} - F_{e}$ 有强的局部可诊断性。

综上所述，两种声明证明完毕。

定理 5.5根据两种声明，我们发现 $Q_{n, k} - F_{e}$ 有强的局部诊断性。设 $F_{e}$ 是 $n (n \geq 6)$ 维增强超立方体 $Q_{n, k}$ 中任意缺失边集且 $| F_{e} | \leq n - 1$ ，则缺失边 $F_{e}$ 的个数是最优的。

证明我们举例说明当 $| F | = n$ 时， $Q_{n, k} - F_{e}$ 不具有强局部可诊断性。由于 $Q_{n, k}$ 是点传递的，不失一般性，假设 $x = \underset{n}{\underset{︸}{00 \dots 00}}$ 。我们假设 $Q_{n, k}$ 中n条遗失边F都与x关联(见图4)，那么在 $Q_{n, k}$ 中x的剩余度就变

成了1，即 $d_{Q_{n, k} - F} (x) = 1$ 。假设y是x唯一的邻点。令 $F_{1} = ({y} \cup N (y)) ∖ {x}$ ， $F_{2} = N (y)$ 。此时

Figure 4. Illustration of the proof in Theorem 5.5

图4. 定理5.5的示意图

$| F_{1} | = | F_{2} | = n + 1$ 。显然， $V (Q_{n, k}) ∖ (F_{1} \cup F_{2})$ 和 $F_{1} △ F_{2}$ 之间没有边。点集对 $(F_{1}, F_{2})$ 不满足定理4.1的(1)~(3)，因此 $Q_{n, k} - F$ 中y在MM*模型下不是局部 $n + 1$ 可诊断的。由于 $Q_{n, k} - F$ 中y的局部可诊断度(少于 $n + 1$ )不等于它的度(等于 $n + 1$ )，那么y没有强局部可诊断性。故 $Q_{n, k}$ 有n条缺失边不能保证有强局部可诊断性。

6. 结论

在这篇文章中，我们研究了n维增强超立方体 $Q_{n, k} (n \geq 6)$ 在MM*模型下的局部诊断度。我们证明了 $Q_{n, k}$ 的诊断度是 $n + 1$ ，以及即使 $Q_{n, k}$ 中存在高达 $n - 1$ 条缺失边，它仍保持这种强的性质。因此，在n维增强超立方体 $Q_{n, k}$ 的缺失边数不超过 $n - 1$ 的条件下，它的诊断度等于每个处理器剩余度的最小值。

致谢

本论文的完成是在我们的导师王老师的细心指导下进行的。在每次论文遇到问题时老师不辞辛苦地讲解才使得我的论文顺利进行。从论文的选题到资料的搜集直至最后论文的修改，整个过程中花费了王老师很多的宝贵时间和精力，在此向导师表示衷心地感谢！导师严谨的治学态度，开拓进取的精神和高度的职责心都将使学生受益终生！

还要感谢我同小组的赵丽娜师姐和两位同门，是你们在平时论文中和我一起探讨问题，并指出我论文上的误区，使我能及时地发现问题把论文顺利地进行下去，没有你们的帮忙我不可能这样顺利地结稿，在此表示深深的谢意。

文章引用

王世英,张雪芳,赵丽娜. 有缺失边的n维增强超立方体在MM^*模型下的局部可诊断性
Local Diagnosability of n-Dimensional Enhanced Hypercubes with Missing Edges under the MM^* Model[J]. 应用数学进展, 2022, 11(02): 726-738. https://doi.org/10.12677/AAM.2022.112079

参考文献

1. Feng, W. and Wang, S. (2020) The Diagnosability of Wheel Networks with Missing Edges under the Comparison Model. Mathematics, 8, Article No. 1818. https://doi.org/10.3390/math8101818

2. Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessors Systems. Proceeding of the 11th International Symposium on Fault-Tolerant Computing, Portland, 24-26 June 1981, 173-175.

3. Sengupta, A. and Dahbura, A.T. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396. https://doi.org/10.1109/12.177309

4. Dahbura, A.T. and Masson, G.M. (1984) An Fault identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492. https://doi.org/10.1109/TC.1984.1676472

5. 樊畅畅, 王世英, 马晓蕾. 有遗失边的n维超立方体和折叠超立方体在MM*模型下的诊断度[J]. 应用数学进展, 2021, 10(1): 150-159. https://doi.org/10.12677/AAM.2021.101018

6. Hsu, G.-H. and Tan, J.J.M. (2007) A Local Diagnosability Measure for Multiprocessor Systems. IEEE Transactions on Parallel and Distributed Systems, 18, 598-607. https://doi.org/10.1109/TPDS.2007.1022

7. Chiang, C.-F. and Tan, J.J.M. (2009) Using Node Diagnosability to Determine t-Diagnosability under the Comparison Diagnosis Model. IEEE Transactions on Computers, 58, 251-259. https://doi.org/10.1109/TC.2008.158

8. Chiang, C.-F., Hsu, G.-H., Shih, L.-M. and Tan, J.J.M. (2012) Diagnosability of Star Graphs with Missing Edges. Information Sciences, 188, 253-259. https://doi.org/10.1016/j.ins.2011.11.012

9. Cheng, E. and Lipták, L. (2013) Diagnosability of Cayley Graphs Generated by Transposition Trees with Missing Edges. Information Sciences, 238, 250-252. https://doi.org/10.1016/j.ins.2013.03.009

10. Cheng, E., Lipták, L. and Steffy, D.E. (2013) Strong Local Diagnosability of -Star Graphs and Cayley Graphs Generated by 2-Trees with Missing Edges. Information Processing Letters, 113, 452-456. https://doi.org/10.1016/j.ipl.2013.03.002

11. Hsieh, S. (2006) Fault-Tolerant Cycles Embedding in the Hypercube with More Both Faulty Vertices and Faulty Edges. Parallel Computing, 32, 84-91. https://doi.org/10.1016/j.parco.2005.09.003

12. Li, T.-K., Tsai, C.H., Tan, J.J.M. and Hsu, L.-H. (2003) Bipanconnectivity and Edge-Fault-Tolerant Bipancyclicity of Hypercubes. Information Processing Letters, 87, 107-110. https://doi.org/10.1016/S0020-0190(03)00258-8

13. Tsai, C.-H., Tan, J.J.M., Liang, T. and Hsu, L.-H. (2002) Fault-Tolerant Hamiltonian Laceability of Hypercubes. Information Processing Letters, 83, 301-306. https://doi.org/10.1016/S0020-0190(02)00214-4

14. Tsai, C.-H. (2007) Cycles Embedding in Hypercubes with Node Failures. Information Processing Letters, 102, 242-246. https://doi.org/10.1016/j.ipl.2006.12.016

15. Tzeng, N.F. and Wei, S. (1991) Enhanced Hypercube. IEEE Transactions on Computers, 40, 284-294. https://doi.org/10.1109/12.76405

16. Liu, H. (2009) The Structural Features of Enhanced Hypercube Networks. Proceedings of the 5th International Conference on Natural Computation, Tianjian, 14-16 August 2009, 345-348. https://doi.org/10.1109/ICNC.2009.191

17. Liu, H. (2008) Properties and Performance of Enhanced Hypercube Networks. Fourth International Conference on Networked Computing and Advanced Information Management, Vol. 1, Gyeongju, 2-4 September 2008, 580-583. https://doi.org/10.1109/NCM.2008.264

18. Wang, D. (1999) Diagnosability of Hypercubes and Enhanced Hypercubes under the Comparison Diagnosis Model. IEEE Transactions on Computers, 48, 1369-1374. https://doi.org/10.1109/12.817401

19. Sabir, E., Mamut, A. and Vumar, E. (2019) The Extra Connectivity of the Enhanced Hypercubes. Theoretical Computer Science, 799, 22-31. https://doi.org/10.1016/j.tcs.2019.09.035

20. Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, New York.

21. Liu, M. and Liu, H. (2013) Paths and Cycles Embedding on Faulty Enhanced Hypercube Networks. Acta Mathematica Scientia, 33, 227-246. https://doi.org/10.1016/S0252-9602(12)60207-0

22. Yuan, J., Liu, A., Ma, X., Liu, X. and Qin, X. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Ary n-Cubes under the PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 26, 1165-1177. https://doi.org/10.1109/TPDS.2014.2318305

NOTES

^*通讯作者。

期刊菜单