下载:
-
众所周知，互连网络在并行计算及通信系统中发挥着重要作用.一个网络的拓扑结构在数学上通常被抽象地模型化为一个图G=(V(G)，E(G))，其中：V(G)是图G的顶点集，表示网络处理器的集合；E(G)是图G的边集，表示网络的通信链路集.在本文中，术语图和网络可以互换使用.本文中所有的图都认为是无向的、简单的和连通的，对于未说明的图论符号和术语，可参考文献[1-3].
设G=(V(G)，E(G))是一个图.对于图G中任意顶点u∈V(G)，设集合{v∈V(G)\{u}|(u，v)∈E(G)}和集合{(u，v)∈E(G)|v∈V(G)\{u}}分别表示顶点u的邻点集和邻边集，记作NG(u)和NEG(u).dG(u)=|NG(u)|称为图G中顶点u的度.对于图G的子图K，设NG(K)=∪u∈KNG(u)-V(K)和NEG(K)=∪u∈KNEG(u)-E(K)分别表示子图K在G中的邻点集和子图K在G中的邻边集.
图G的经典连通度κ(G)和边连通度λ(G)是衡量网络可靠性和容错性的两个重要参数[4].连通度κ(G)和边连通度λ(G)越大，网络的可靠性就越高.但是，这两个参数有明显的不足之处，比如，在互连网络的实际应用当中，与一个处理器相连接的所有处理器(链路)同时发生故障的可能性较低，所以用这两个参数衡量网络可靠性和容错性是不精确的.为克服这些不足之处，可以通过对G-S的每一个分支强加一些限制条件来推广图G的经典连通度(边连通度)，这里S⊂V(G)(S⊂E(G)).文献[5]首次考虑了这个问题并且提出了图G的条件连通度(边连通度)的概念.
设
$ \mathscr{G} $ 是图G所具有的一种性质.文献[5]定义了图G的条件连通度(边连通度)：如果G中存在某种点子集(边子集)，使得G删除这种点子集(边子集)后得到的图不连通且每个连通分支都具有性质$ \mathscr{G} $ ，则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的条件连通度(边连通度)，记为$ \kappa \left( {G, \mathscr{G}} \right)\left( {\lambda \left( {G, \mathscr{G}} \right)} \right) $ .随后，文献[6-7]研究了下面所述的一种条件连通度(边连通度)：设G是连通图且g是非负整数，如果图G中存在某种点子集(边子集)，使得G中删除这种点子集(边子集)后得到的图不连通并且每个分支的点数超过g，则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的g-额外连通度(g-额外边连通度)，记为
$ {\kappa _g}(G)\left( {{\lambda _g}(G)} \right).{\kappa _1}(G)\left( {{\lambda _1}(G)} \right) $ 也称作图G的超连通度(超边连通度).明显地，如果G不是完全图，则$ {\kappa _0}(G) = \kappa (G)且 {\lambda _0}(G) = \lambda (G) $ .因此，g-额外连通度(g-额外边连通度)可以认为是经典连通度(边连通度)的一种推广形式，并且它能更加精确地衡量大型并行处理系统的可靠性和容错性.网络(图)的g-额外连通度(g-额外边连通度)已被许多学者所研究，详细结果可参看文献[8-19]及相关文献.在平行计算系统中，n维超立方体Qn[18]、n维折叠超立方体FQn[19]和交叉超立方体EH(s，t)[2]是3个重要的互连网络.基于这3个网络，文献[20]提出了一个新的网络交换折叠超立方体EFH(s，t)，EFH(s，t) 是在EH(s，t)的基础上增加了一些额外的边获得的，并且这些边称为补边.交换折叠超立方体有许多重要的特性，比如它有短的直径和低消费因子.关于交换折叠超立方体EFH(s，t)特性的详细结果可参看文献[10, 20-22].
文献[11]证明了：
$ \kappa_{1}(E H(s, t))=\lambda_{1}(E H(s, t))=2 s, 1 \leqslant s \leqslant t $ .文献[17]证明了：$ {\kappa _2}(EH(s, t)) = 3s - 2, 2 \le s \le t;{\lambda _2}(EH(s, t)) = 3s - 1, 3 \le s \le t $ .文献[21-22]探究了交换折叠超立方体EFH(s，t)的连通度和边连通度，并且证明了：$ \kappa(E F H(s, t))=\lambda(E F H(s, t))=s+2, 1 \leqslant s \leqslant t $ .文献[10]证明了：$ \kappa_{1}(E F H(s, t))=\lambda_{1}(E F H(s, t))=2 s+2, 1 \leqslant s \leqslant t $ .本文探讨交换折叠超立方体EFH(s，t)的2-额外边连通度，最终确定了λ2(EFH(s，t))=3s+2，6≤s≤t.
全文HTML
-
一个n元二进制字符串x=xn-1xn-2… x0的第i个字符xi记为x[i]，0≤ i ≤ n-1.
记
$ x[i: j]=x_{i} x_{i-1} \cdots x_{j} . \bar{x}=\bar{x}_{n-1} \bar{x}_{n-2} \cdots \bar{x}_{0} $ ，其中$ \bar{x}_{i}=1-x_{i} . \text {设 } y=y_{n-1} y_{n-2} \cdots y_{0} $ .令$ H(x, {\rm{ }}y) = \sum\limits_{i = 1}^{n - 1} {\left| {{x_i} - {y_i}} \right|} $ 称为$ x=x_{n-1} x_{n-2} \cdots x_{0} \text { 与 } y=y_{n-1} y_{n-2} \cdots y_{0} $ 的哈明距离.定义1[3] 设交换超立方体EH(s，t)=G(V，E)，s，t是正整数.交换超立方体的点集为
$ V(E H(s, t))=\left\{a_{s-1} a_{s-2} \cdots a_{1} a_{0} b_{t-1} b_{t-2} \cdots b_{1} b_{0} c \mid a_{i}, b_{j}, c \in\{0, 1\}, 0 \leqslant i \leqslant s-1, 0 \leqslant j \leqslant t-1\right\} $ 交换超立方体的边集是由3种类型的边E1，E2，E3构成的.其中
定义2[20] 交换折叠超立方体记为EFH(s，t)，它是由交换超立方体EH(s，t)中的任意两个互补的点
$ u=a_{s-1} a_{s-2} \cdots a_{0} b_{t-1} b_{t-2} \cdots b_{0} c \text { 和 } \bar{u}=\bar{a}_{s-1} \bar{a}_{s-2} \cdots \bar{a}_{0} \bar{b}_{t-1} \bar{b}_{t-2} \cdots \bar{b}_{0} \bar{c} $ 增加一条边后得到的.这些新增加的边称为EFH(s，t)的补边，补边构成的集合记为.EFH(s，t)- 中的边称为交叉边.图EH(1，2)和EFH(1，2)如图 1所示.
设任意一条边(u，v)∈E(EFH(s，t)-M)，则存在唯一确定的i∈{0，1，2，3，…，s+t}使得u[i]≠v[i]且u[j]=v[j](j=1，2，…，i-1，i+1，…，s+t)，此时称边(u，v)是i-边.如果EFH(s，t)- M中两个点u和v通过i-边相邻，则称u和v沿维数i相邻.我们也称u是v的i-邻点，记作v=ui.由定义可知uij是ui的j-邻点，明显地，uii=u.EFH(s，t)-M中的边(u，ui)称为顶点u的i-边，记作ei(u).设
$ $ 表示与顶点u关联的补边.下面的讨论中，我们规定$ \bar e(u) = (u, \bar u) \in \bar M $ 是EFH(s，t)中的边，其中us+t与u的二进制字符串最左边的位不同.同理e0(u)=(u，u0)是EFH(s，t)中的边，其中u0与u的二进制字符串最右边的位不同.设u∈V(EFH(s，t)).通过定义2，如果u[0]=0，则
$ {d_{EFH(s, t)}}(u) = s + 2 $ ，否则$ {d_{EFH(s, t)}}(u) = t + 2 $ .下面给出EH(s，t)和EFH(s，t)的一些结论：
引理1[4]
$ \kappa(E H(s, t))=\lambda(E H(s, t))=s+1, 1 \leqslant s \leqslant t $ .引理2[11]
$ \kappa_{1}(E H(s, t))=\lambda_{1}(E H(s, t))=2 s, 1 \leqslant s \leqslant t $ .引理3[11] EH(s，t)同构于EH(t，s).
引理4[20] EFH(s，t)同构于EFH(t，s).
通过引理3和引理4，可以在下面讨论中设s≤t，则δ(EH(s，t))=s+1且δ(EFH(s，t))=s+2.
引理5[4] EH(s，t)可分解成两个EH(s-1，t)或两个EH(s，t-1).
根据EFH(s，t)的定义容易得出EFH(s，t)具有下面性质：
性质1 交换折叠超立方体网络EFH(s，t)可以分解成两个子图L和R，其中
L和R分别是由点集V(L)和V(R)诱导的子图.明显地，L和R都同构于EH(s-1，t)，并且L和R之间的边是由E2和M构成的.记作
$ E F H(s, t)=L \oplus R . \text { 令 } u \in V(L)(\text { 或 } u \in V(R)) $ ，则u在R(或L)中通过交叉边的邻点记作uL(或uR).明显地，$ u_{s+t}=u_{L}\left(\text { 或 } u_{s+t}=u_{R}\right) . \text { 令 } M_{s+t}=\left\{\left(u, u_{s+t}\right) \mid u \in L, u_{s+t} \in R\right\} $ .文献[13]证明了折叠超立方体FQn(n≥4)中不含3-圈，并且任何不相邻的两个点的共同邻点的个数不超过2.因此容易得到下面的引理：
引理6 交换折叠超立方体EFH(s，t)中不含3-圈，并且任何不相邻的两个点的共同邻点的个数不超过2个.
引理7 若P为EFH(s，t)中任意一条长度是2的路，则|NEEFH(s，t)(P)|≥3s+2.
证 由EFH(s，t)的定义及引理6，容易证明|NEEFH(s，t)(P)|≥3s+2.
引理8 设K⊂E(EH(s，t))并且|K| < 2s，s≥2.则EH(s，t)-K满足下面两种情形之一：
(ⅰ) EH(s，t)-K是连通的；
(ⅱ) EH(s，t)-K有两个分支，其中一个分支是一个孤立点.
证 如果EH(s，t)-K是连通的，则情形(ⅰ)成立.现在可假设EH(s，t)-K是不连通的.因为λ(EH(s，t))=s+1并且|K| < 2s=λ1(EH(s，t))，所以EH(s，t)-K中至少包含一个孤立点.假设有两个孤立点，记为x，y.由于
EH(s，t)至少移除2s+1条边才能得到两个孤立点，而|K| < 2s，因此在EH(s，t)-K中只存在一个孤立点.
设u是EH(s，t)-K中唯一一个孤立点.因为
所以EH(s，t)-K-{u}是连通的.因此情形(ⅱ)成立.
-
定理1 设
$ EFH\left( {s, t} \right) = L \oplus R $ .对于任意的$ F \subseteq E(E F H(s, t)), \text { 令 } F_{L}=F \cap E(L), F_{R}=E \cap V(R), {F_{{M_{s + t}}}} = F \cap {M_{s + t}}, {F_{\bar M}} = F \cap \bar M $ .如果|F|≤3s+1并且EFH(s，t)-F中既无孤立点也无孤立边，则R-FR(或L-FL)中每一个顶点均与L-FL(或R-FR)中一个顶点连通.证 对于任意的顶点
$ u=1 a_{s-2} \cdots a_{0} b_{t-1} \cdots b_{0} c \in V\left(R-F_{R}\right) $ ，分以下两种情形进行讨论：情形1
$ u=1 a_{s-2} \cdots a_{0} b_{t-1} \cdots b_{0} 0 . \text { 如果 } e_{s+t}(u) \notin F_{M_{s+t}} \text { 或 } \bar{e}(u) \notin F_{\bar{M}} $ ，则定理1得证.因此我们假设$ {e_{s + t}}(u) \in {F_{{M_{s + t}}}}且 \bar e(u) \in {F_{\bar M}} $ .如果$ {u_0} = 1{a_{s - 2}} \cdots {a_0}{b_{t - 1}} \cdots {b_0}1 \notin {F_R}, {u_{0{i^\prime }}} = 1{a_{s - 2}} \cdots {a_0}{b_{t - 1}} \cdots {{\bar b}_{i'}} \cdots {b_0}1 \notin {F_R} $ ,$ u_{0 i^{\prime} 0}=1 a_{s-2} \cdots a_{0} b_{t-1} \cdots \bar{b}_{i^{\prime}} \cdots b_{0} 0 \notin F_{R} $ 且$u_{0 i^{\prime} 0(s+t)}=0 a_{s-2} \cdots a_{0} b_{t-1} \cdots \bar{b}_{i^{\prime}} \cdots b_{0} 0 \notin F_{L}\left(\text { 或者 } u_{0} \notin F_{R}, \bar{u}_{0} \notin F_{L}\right) $ ，也就是说$ e_{0}(u) \notin F_{R}, e_{i^{\prime}}\left(u_{0}\right) \notin F_{R}, e_{0}\left(u_{0 i^{\prime}}\right) \notin F_{R}, e_{s+t}\left(u_{0 i^{\prime} 0}\right) \notin F_{M_{s+t}}\left(\text { 或者 } e_{0}(u) \notin F_{R}, \bar{e}\left(u_{0}\right) \notin F_{\bar{M}}\right) $ ，那么从u出发总存在1条路径$ u \rightarrow u_{0} \rightarrow u_{0 i^{\prime}} \rightarrow u_{0 i^{\prime} 0} \rightarrow u_{0 i^{\prime} 0(s+t)}\left(\text { 或者 } u \rightarrow u_{0} \rightarrow \bar{u}_{0}\right) $ 使其连接至L-FL，则定理1得证.因此我们假设$ e_{0}(u) \in F_{R} . \text { 令 } A=\left\{e_{i}(u), e_{s+t}\left(u_{i}\right)\left(\bar{e}\left(u_{i}\right)\right) \mid t+1 \leqslant i \leqslant s+t-1\right\} \cap F $ ，如果|A| < s-1，那么存在某个i，t+1≤i≤s+t-1，使得$ e_{i}(u) \notin F_{R} \text { 且 } e_{s+t}\left(u_{i}\right) \notin F_{M_{s+t}}\left(\text {或者 } e_{i}(u) \notin F_{R} \text { 且 } \bar{e}\left(u_{i}\right) \notin F_{\bar{M}}\right) $ ，则定理1得证.因此假设|A|≥s-1.因为EFH(s，t)-F中不存在孤立点，则存在某条边
$ e_{i}(u)=\left(u, u_{i}\right) \notin F_{R} $ ，其中t+1≤i≤s+t-1，那么可知$ u_{i}=1 a_{s-2} \cdots \bar{a}_{i} \cdots a_{0} b_{t-1} \cdots b_{0} 0 $ .如果$ e_{s+t}\left(u_{i}\right)=\left(u_{i}, u_{i(s+t)}\right) \notin F_{M_{s+t}} \text { 或者 } \bar{e}\left(u_{i}\right)=\left(u_{i}, \bar{u}_{i}\right) \notin F_{\bar{M}} $ ，则定理1得证.因此假设$ e_{s+t}\left(u_{i}\right)=\left(u_{i}, u_{i(s+t)}\right) \in F_{M_{s+t}} \text { 且 } \bar{e}\left(u_{i}\right)=\left(u_{i}, \bar{u}_{i}\right) \in F_{\bar{M}} . \text { 如果 } e_{0}\left(u_{i}\right)=\left(u_{i}, u_{i 0}\right) \notin F_{R} $ ，此时可形成一条通向L-FL的路径：$ u \rightarrow u_{i} \rightarrow u_{i 0} \rightarrow u_{i 0 i^{\prime}} \rightarrow u_{i 0 i^{\prime} 0} \rightarrow u_{i 0 i^{\prime} 0(s+t)}\left(\text { 或者 } u \rightarrow u_{i} \rightarrow u_{i 0} \rightarrow \bar{u}_{i 0}\right) $ 其中1≤i'≤t，则定理1可证.因此假设$ e_{0}\left(u_{i}\right)=\left(u_{i}, u_{i 0}\right) \in F_{R} $ .令如果|B| < s-2，那么存在某个j(t+1≤j≤s+t-1，j≠i)，使得
$ e_{j}\left(u_{i}\right) \notin F_{R} \text { 且 } e_{s+t}\left(u_{i j}\right) \notin F_{M_{s+t}} $ (或者$ e_{j}\left(u_{i}\right) \notin F_{R} \text { 且 } \bar{e}\left(u_{i j}\right) \notin F_{\bar{M}} $ )，则u可通过一条路径连接至L-FL，定理1得证.因此假设|B|≥s-2.因为EFH(s，t)-F中不存在孤立边，因此存在
$ e_{j}\left(u_{i}\right)=\left(u_{i}, u_{i j}\right) \notin F_{R}, j \neq i $ .那么u经过uij至L-FL可构造如下路径：$ e_{i}(u) \rightarrow e_{j}\left(u_{i}\right) \rightarrow e_{(s+t)}\left(u_{i j}\right) ; e_{i}(u) \rightarrow e_{j}\left(u_{i}\right) \rightarrow e_{0}\left(u_{i j}\right) \rightarrow e_{i^{\prime}}\left(u_{i j 0}\right) \rightarrow e_{0}\left(u_{i j 0 i^{\prime}}\right) \rightarrow e_{(s+t)}\left(u_{i j 0 i^{\prime} 0}\right) $ ，其中1≤i'≤t；$ e_{k}\left(u_{i j}\right) \rightarrow e_{s+t}\left(u_{i j k}\right), \text { 其中 } t+1 \leqslant k \leqslant s+t-1, k \neq i, j $ .设
$ C=\left\{e_{s+t}(u), e_{0}(u), \bar{e}(u), e_{s+t}\left(u_{i}\right), e_{0}\left(u_{i}\right), \bar{e}\left(u_{i}\right)\right\} $ .因为然而u可通过uij构造s-2条通向L-FL的路径，则u可通过一条路径使得u与L-FL中的某个点路连通，定理1得证.
情形2
$ u=1 a_{s-2} \cdots a_{0} b_{t-1} \cdots b_{0} 1 $ .由于N(u)∩V(L)={u}.如果$ \bar{e}(u) \notin F_{\bar{M}} $ ，则定理1得证.因此我们可假设$ \bar{e}(u) \in F_{\bar{M}} $ .如果$ {e_0}(u) \notin {F_R} $ ，则存在一条路径$ e_{0}(u) \rightarrow e_{s+t}\left(u_{0}\right)\left(\text { 或者 } e_{0}(u) \rightarrow \bar{e}\left(u_{0}\right)\right) $ ，使得u连通至L-FL，则定理1得证.因此我们假设$ {e_0}(u) \in {F_R} $ .令如果|A'| < t，则必定存在某一i'(1≤i'≤t)，使得
$ e_{i^{\prime}}(u) \notin F_{R}, e_{0}\left(u_{i^{\prime}}\right) \notin F_{R}, e_{(s+t)}\left(u_{i^{\prime} 0}\right) \notin F_{M_{s+t}} $ (或者$ \left.e_{i^{\prime}}(u) \notin F_{R}, \bar{e}\left(u_{i^{\prime}}\right) \notin F_{\bar{M}}\right) $ )，使得u与L-FL连通.否则|A'|≥t.因为EFH(s，t)-F中不存在孤立点，因此存在某一条边
$ e_{i^{\prime}}(u)=\left(u, u_{i^{\prime}}\right) \notin F_{R}\left(1 \leqslant i^{\prime} \leqslant t\right)$ ，如果$ \bar e\left( {{u_{i'}}} \right) \notin {F_{\bar M}} $ ，则定理1得证.因此我们假设$ \bar{e}\left(u_{i^{\prime}}\right) \in F_{\bar{M}} . \text { 如果 } e_{0}\left(u_{i^{\prime}}\right)=\left(u_{i^{\prime}}, u_{i^{\prime} 0}\right) \notin F_{R} $ ，则可构造一条通向L-FL的路径：$ e_{i^{\prime}}(u) \rightarrow e_{0}\left(u_{i^{\prime}}\right) \rightarrow e_{s+t}\left(u_{i^{\prime} 0}\right)\left(\text { 或者 } e_{i^{\prime}}(u) \rightarrow e_{0}\left(u_{i^{\prime}}\right) \rightarrow \bar{e}\left(u_{i^{\prime} 0}\right)\right) $ ，则定理1得证.因此假设$ e_{0}\left(u_{i^{\prime}}\right)=\left(u_{i^{\prime}}, u_{i^{\prime} 0}\right) \in F_{R} $ .令如果|B'| < t-1，那么存在某个j'(1≤j'≤t，j'≠i')，使得
$ {e_{j'}}\left( {{u_{i'}}} \right) \notin {F_R} 且 {e_{s + t}}\left( {{u_{i'j'}}} \right) \notin {F_{{M_{s + t}}}} $ (或者$ {e_{{j^\prime }}}\left( {{u_i}} \right) \notin \left. {{F_R}{\rm{且 }}\bar e\left( {{u_{i'j'}}} \right) \notin {F_{\bar M}}} \right) $ )，则u可通过一条路径连接至L-FL，定理1得证.因此假设|B'|≥t-1.因为EFH(s，t)-F中不存在孤立边，因此存在
$ e_{j^{\prime}}\left(u_{i^{\prime}}\right)=\left(u_{i^{\prime}}, u_{i^{\prime} j^{\prime}}\right) \notin F_{R}, j^{\prime} \neq i^{\prime} $ .那么u经过ui'j'至L-FL可构造如下路径：$ e_{i^{\prime}}(u) \rightarrow e_{j^{\prime}}\left(u_{i^{\prime}}\right) \rightarrow \bar{e}\left(u_{i^{\prime} j^{\prime}}\right) ; e_{i^{\prime}}(u) \rightarrow e_{j^{\prime}}\left(u_{i^{\prime}}\right) \rightarrow e_{0}\left(u_{i^{\prime} j^{\prime}}\right) \rightarrow e_{s+t}\left(u_{i^{\prime} j^{\prime} 0}\right) e_{i^{\prime}}(u) \rightarrow e_{j^{\prime}}\left(u_{i^{\prime}}\right) \rightarrow e_{k^{\prime}}\left(u_{i^{\prime} j^{\prime}}\right) \rightarrow e_{0}\left(u_{i^{\prime} j^{\prime} k^{\prime}}\right) \rightarrow e_{s+t}\left(u_{i^{\prime} j^{\prime} k^{\prime} 0}\right) $ ，其中1≤k'≤t，k'≠i'，j'.设
$ C^{\prime}=\left\{\bar{e}(u), e_{0}(u), e_{0}\left(u_{i^{\prime}}\right), \bar{e}\left(u_{i^{\prime}}\right)\right\} $ .因为然而u可通过ui'j'构造t条通向L-FL的路径.则u至少可通过一条路径使得u与L-FL中的某个点路连通，定理1得证.
定理2 λ2(EFH(s，t))=3s+2，其中s≥6.
证 设P为EFH(s，t)中一条长度为2的路径，由引理7可知|NEEFH(s，t)(P)|≥3s+2.通过EFH(s，t)的定义，EFH(s，t)-P既不包含孤立顶点也不包含孤立边.因此可知λ2(EFH(s，t))≤3s+2.
接下来只需证明λ2(EFH(s，t))≥3s+2，即证明对于任意的顶点集S⊆E(EFH(s，t))，当|S|=3s+1且不存在孤立顶点也不存在孤立边时，EFH(s，t)-S是连通的.设
$ E F H(s, t)=L \oplus R $ .方便起见，我们设
$ S_{L}=S \cap E(L), S_{R}=S \cap E(R), S_{M_{s+t}}=S \cap M_{s+t}, S_{\bar{M}}=S \cap \bar{M} $ .不失一般性，令|SL|≤|SR|，那么可知$ \left|S_{L}\right| \leqslant \frac{(3 s+1)}{2}<2 s-2, s \geqslant 6 $ .通过引理8，我们可知L-SL满足下面两种情形之一：L-SL是连通的；L-SL有两个分支，其中一个分支是一个孤立顶点.现在考虑这两种情形.情形1 L-SL是连通的
由定理1可知R-SR中任意一顶点与L-SL中一顶点连通.因此EFH(s，t)-F是连通的.
情形2 L-SL有两个连通分支，其中一个是孤立点.
设
$ u=0 a_{s-2} \cdots a_{0} b_{t-1} \cdots b_{0} c $ 是L-SL中的一个孤立点.此时有|SL|≥|NEL(u)|≥s.接下来我们证明EFH(s，t)-S中u与L-SL-{u}是连通的：情形2.1 当
$ u=0 a_{s-2} \cdots a_{0} b_{t-1} \cdots b_{0} 1 $ 时，我们有$ N(u) \cap V(R)=\{\bar{u}\} . \text { 如果 } \bar{e}(u)=(u, \bar{u}) \in S_{\bar{M}} $ ，则u为EFH(s，t)-S中的孤立点，这与EFH(s，t)-S不存在孤立点矛盾.因此$ \bar{e}(u)=(u, \bar{u}) \in S_{\bar{M}} $ .方便起见设$ v=\bar{u} . \text { 如果 } e_{s+t}(v)=\left(v, v_{s+t}\right) \notin S_{M_{s+t}} $ ，则定理2得证.因此假设$ e_{s+t}(v)=\left(v, v_{s+t}\right) \in S_{M_{s+t}} $ .如果$ {e_0}(v) \notin {S_R}, {e_{i'}}\left( {{v_0}} \right) \notin {S_R}, {e_0}\left( {{v_{0i'}}} \right) \notin {S_R}, {e_{s + t}}\left( {{v_{0, i'0}}} \right) \notin {S_{{M_{ + t}}}}\left( {{\rm{或者 }}{e_0}(v) = \left( {v, {v_0}} \right) \notin {S_R}, \bar e\left( {{v_0}} \right) = \left( {{v_0}, {{\bar v}_0}} \right) \notin {S_{\bar M}}} \right) $ ，则定理2得证.因此假设$ e_{0}(v)=\left(v, v_{0}\right) \in S_{R} $ .设如果|A| < s-1，则存在某个i(t+1≤i≤s+t-1)使得
$ e_{i}(v) \notin S_{R}, e_{s+t}\left(v_{i}\right) \notin S_{M_{s+1}}\left(\text { 或者 } e_{i}(v) \notin S_{R}\right. \left.\bar{e}\left(v_{i}\right) \notin S_{\bar{M}}\right) $ ，则定理2得证.因此假设|A|≥s-1.因为EFH(s，t)-S不存在孤立边，因此存在某个i(t+1≤i≤s+t-1)使得
$ e_{i}(v)=\left(v, v_{i}\right) \notin S_{R} $ ，则u通过vi构造连接u到L-{u}的路径为：$ \bar{e}(u) \rightarrow e_{i}(v) \rightarrow e_{j}\left(v_{i}\right) \rightarrow e_{s+t}\left(v_{i j}\right) $ ，其中t+1≤j≤s+t-1，j≠i；$ e_{i}(v) \rightarrow e_{0}\left(v_{i}\right) \rightarrow e_{i^{\prime}}\left(v_{i 0}\right) \rightarrow e_{0}\left(v_{i 0 i^{\prime}}\right) \rightarrow e_{s+t}\left(v_{i 0 i^{\prime} 0}\right)\left(\text { 或者 } e_{i}(v) \rightarrow e_{0}\left(v_{i}\right) \rightarrow \bar{e}\left(v_{i 0}\right)\right) $ ，其中1≤i'≤t；$ {e_i}(v) \to {e_{s + t}}\left( {{v_i}} \right);{e_i}(v) \to \bar e\left( {{v_i}} \right) $ .由于
$ \left|S-\left(S_{L} \cup A \cup\left\{e_{0}(v), e_{s+t}(v)\right\}\right)\right| \leqslant 3 s-s-(s-1)-2=s-1 $ ，且u通过vi可构造s+1条通向L-{u}的路径，故至少存在一条路径使u与L-SL-{u}连通，定理2得证.情形2.2 当
$ u=0 a_{s-2} \cdots a_{0} b_{t-1} \cdots b_{0} 0 $ 时，因为EFH(s，t)-S中不存在孤立点，故$ e_{s+t}(u)=\left(u, u_{s+t}\right) \notin F_{M_{s+t}} $ 或者$ \bar{e}(u)=(u, \bar{u}) \notin F_{\bar{M}} $ .下面考虑两种情形：(ⅰ)$ e_{s+t}(u) \notin S_{M_{s+t}} \text { 且 } \bar{e}(u) \notin S_{\bar{M}} $ ；(ⅱ)$ e_{s+t}(u) \notin S_{M_{s+t}} \text { 且 } \bar{e}(u) \in S_{\bar{M}}, \text { 或者 } e_{s+t}(u) \in S_{M_{s+t}} \text { 且 } \bar{e}(u) \notin S_{\bar{M}} $ .(ⅰ)
$ e_{s+t}(u) \notin S_{M_{s+t}} \text { 且 } e(u) \notin S_{\bar{M}} $ .由EFH(s，t)的定义可知us+t和u在R中没有共同的邻点.方便起见，设$ v=u_{s+t}, w=\bar{u} $ ，通过引理7，我们可知v(=uR)和w(= u)在L中有两个共同的邻点，即$ N_{L}(v) \bigcap N_{L}(w)=\left\{u, \bar{v}\left(=w_{s+t}\right)\right\} . \text { 如果 } \bar{e}(v) \notin S_{\bar{M}} \text { 或者 } e_{s+t}(w) \notin S_{M_{s+}} $ ，则定理2得证.因此假设$ \bar{e}(v) \in S_{\bar{M}} \text { 且 } e_{s+t}(w) \in S_{M_{s+t}} $ .我们可构造s+t条连接接v(或者w)至$ L-S_{L}-\left\{u, \bar{v}\left(=w_{R}\right)\right\} $ 的路径.即：$ e_{i}(v) \rightarrow e_{s+t}\left(v_{i}\right) \text { 或者 } e_{i}(v) \rightarrow \bar{e}\left(v_{i}\right), \text { 其中 } t+1 \leqslant i \leqslant s+t-1 ; e_{0}(v) \rightarrow e_{i^{\prime}}\left(v_{0}\right) \rightarrow e_{0}\left(v_{0 i^{\prime}}\right) \rightarrow e_{s+t}\left(v_{0 i^{\prime} 0}\right) $ 或者$ e_{0}(v) \rightarrow \bar{e}\left(v_{0}\right), \text { 其中 } 1 \leqslant i^{\prime} \leqslant t ; e_{0}(w) \rightarrow e_{s+t}\left(w_{0}\right) ; e_{j^{\prime}}(w) \rightarrow e_{0}\left(w_{j^{\prime}}\right) \rightarrow e_{s+t}\left(w_{j^{\prime} 0}\right) \text { 或者 } e_{j^{\prime}}(w) \rightarrow e\left(w_{j^{\prime}}\right) $ ，其中1≤j'≤t.由于$ \left|S-\left(S_{L} \cup\left\{\bar{e}(v), e_{s+t}(w)\right\}\right)\right| \leqslant 3 s+1-s-2=2 s-1 $ ，且u通过v(或者w)可构造s+t(≥2s)条通向L-{u}的路径，故至少存在一条路径使u与L-SL-{u}连通，定理2得证.(ⅱ)
$ e_{s+t}(u) \notin S_{M_{s+t}} \text { 且 } \bar{e}(u) \in S_{\bar{M}}, \text { 或者 } e_{s+t}(u) \in S_{M_{s+1}} \text { 且 } \bar{e}^{-}(u) \notin S_{\bar{M}} $ .不失一般性我们假设$ e_{s+t}(u) \notin S_{M_{s+t}} \text { 且 } \bar{e}(u) \in S_{\bar{M}} . \text { 如果 } \bar{e}\left(u_{s+t}\right) \notin S_{\bar{M}} $ ，则定理2得证.因此我们假设$ \bar{e}\left(u_{s+t}\right) \in S_{\bar{M}} . \text { 如果 } e_{0}\left(u_{s+t}\right) \notin S_{R} , e_{i^{\prime}}\left(u_{(s+t) 0}\right) \notin S_{R}, e_{0}\left(u_{(s+t) 0 i^{\prime}}\right) \notin S_{R}, e_{s+t}\left(u_{(s+t) 0 i^{\prime} 0}\right) \notin S_{M_{s+t}}\left(\text { 或者 } e_{0}\left(u_{s+t}\right) \notin S_{R}, \bar{e}\left(u_{(s+t) 0}\right) \notin S_{\bar{M}}\right) $ 则定理2得证.因此我们假设e0(us+t)∈SR.因为EFH(s，t)-S中不存在孤立边，因此$ N E_{R}\left(u_{s+t}\right) \cap S \neq \varnothing $ .假设$ e_{i}\left(u_{s+t}\right)=\left(u_{s+t}, u_{(s+t) i}\right) \notin S_{R}, \text { 其中 } t+1 \leqslant i \leqslant s+t-1 $ .对于任意的点$ v \in N_{R}\left(\left\{u_{s+t}, u_{(s+t) i}\right\}\right) $ ，设$ D= \left\{e_{s+t}(v) \mid e_{s+t}(v) \in M_{s+t}\right\}(\text { 或者 } D=\{\bar{e}(v) \mid \bar{e}(v) \in \bar{M}\}) $ ，并且|D|=2s-2.容易知道$ D \not\subset \left( {{N_L}\left( u \right) \cup \left\{ {\bar u, {{\bar u}_R}, {u_{R0}}} \right\}} \right) $ .由于$ \left|S-\left(S_{L} \cup\left\{\bar{e}(u), \bar{e}\left(u_{s+t}\right), e_{0}\left(u_{s+t}\right)\right\}\right)\right| \leqslant 3 s-s-3=2 s-3 $ ，所以S中至多有2s-3条边在D中.因此在D中至少存在一条边不属于S.即u与L-SL-{u}连通.
-
本文在交换折叠超立方体网络经典边连通度和超边连通度的基础上深入研究，进一步研究了其2-额外边连通度，证明了：当t≥s≥6时，λ2(EFH(s，t))=3s+2.也就是说，EFH(s，t)中至少删除3s+2条边，才能得到不包含孤立顶点和孤立边的非连通图.