无向二元Kautz 网络的可靠性分析

当n≥3时,无向二元Kautz图UK(2．n)被证明是极大限制边连通的．利用此结果确定了无向Kautz网络UK(2.N)的可靠多项式的前3项系数，给出第4项系数的一个下界，并且此下界是紧的．     

有向笛卡尔积图的k-限制弧连通度

笛卡尔积图是大型互联网络最重要的数学模型之一.有向图的k-限制弧连通度是弧连通度和限制弧连通度的推广,可用于度量网络的可靠性.强连通有向图D的弧子集S被称为D的一个k-限制弧割,若D-S有一个顶点数至少为k的强连通分支D_1,使得D-V(D_1)包含一个顶点数至少为k的连通子图.若这样的一个弧割存在,则称D是λ~k-连通的.D中最小k-限制弧割所含的弧数称为D的k-限制弧连通度,记做λ~k(D).在有向笛卡尔积图中,推广2-限制弧连通度的结论到k-限制弧连通度,得到有向笛卡尔积图的k-限制弧连通度的上界和3-限制弧连通度的下界,并用例子说明所得界是紧的.     

有向循环图的强连通度的性质

本文首先证明了连通有向循环图的k原子部分仍为连通有向循环图,并给出了有关连通有向循环图的强连通度的另一些性质。然后利用这些性质得到了基础图是简单图的连通有向循环图的强连通度的下界。     

图的谱半径的界

我们定义简单图G的点的邻度为该点的邻点的度之和。本文的主要结果是:若r是连通简单(p,q)-图G的谱半径,则有■其中δ、△、■和■分别是图G的最小度、最大度、最小邻度和最大邻度。     

一类非正则p群的非正规Cayley图

冯衍全等证明,设p是一个奇素数,G是一个有限正则p-群,那么,G的任何连通的2度有向Cayley图都是G的正夫Cayley图,本文给出了一类非正则p-群,它的每个群都存在一个连通的2度的非正规的有向Cayley图。     

有向Kautz图上的随机游动

首先给出了有向Kautz图上简单随机游动任意两点之间平均击中时间的表达式及其最大和最小值,并证明了快速收敛性.最后给出了有向Kautz图上简单随机游动从任一单点分布到稳定分布的一个最优停时规则,从而得到了最优均值.     

折叠交叉立方体的1-好邻诊断度

诊断度是多处理器系统互连网络能够诊断的最大故障结点的个数,它是度量多处理器系统故障诊断能力的一个重要参数.2012年,Peng等提出了一种新的诊断方法g-好邻诊断度,它要求每个非故障顶点至少有g个非故障邻点.n-维折叠交叉立方体网络FCQ_n是由交叉立方体网络CQ_n增加2^n-1条边后所得.该文利用1-好邻诊断度作为评价可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到折叠交叉立方体网络的1-好邻诊断度.证明了在PMC模型与MM^*模型下FCQ_n的1-好邻诊断度分别等于2n+1,n≥5和2n+1,n≥6.     

交换折叠超立方体的超连通度

超连通度(超边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数。设G是连通图,图G的超连通度(超边连通度)是指从G中删除最小数目的点(边)使得G不连通,且G的每个连通分支中都至少包含两个顶点。李等人(2015)提出了一个新的网络交换折叠超立方体网络EFH(s,t)。该文利用超连通度和超边连通度作为评价可靠性的重要度量,对交换折叠超立方体网络的可靠性进行分析,得到了交换折叠超立方体网络的超连通度和超边连通度,证明了EFH(s,t)的超连通度和超边连通度等于2s+2,1≤s≤t。这个结果意味着,为了使EFH(s,t)不连通且不含孤立点,至少有2s+2个点(边)要同时发生故障。     

k元n方体网络关于极大局部连通性的容错度

k元n方体因其良好的拓扑性质和特殊的结构成为多处理机系统最常用的互连网络之一.图的局部连通度是衡量网络可靠性的重要参数.极大局部连通图是以局部连通度为度量指标时最可靠的一类网络.证明了具有至多2n-2个故障点的k元n方体网络仍具有极大局部连通性.     

关于图的上可嵌入性与非邻节点度和的一个注记

进一步研究了2(或3)—边连通简单图的上可嵌人性与非邻节点度和的关系，得到如下结果：2—边连通简单图G为上可嵌入的条件及其下界表达式，而这个界是最好的，不能再继续改进；对于3-边连通的简单图，本文还给出了更为清楚的表达式．     

交换超立方体在PMC模型下的g好邻条件诊断度

诊断度是多处理器系统互连网络能够诊断的最大故障结点的个数,它是度量多处理器系统故障诊断能力的一种参数。g好邻条件诊断度是2012年提出的一种新的诊断度,它要求每个非故障顶点至少有g个非故障邻点。研究了交换超立方体EH(s,t)在PMC模型下的g好邻条件诊断度,证明了EH(s,t)(1≤s≤t,0≤g≤s)在PMC模型下的g好邻条件诊断度为2g(s+2-g)-1.     

交叉立方体的限制性连通度（英文）

G是一个图,h是一个正整数,一个图G的h-限制性连通度是使得G删除G中的某个点集使得G不连通且每个分支中点的度数至少是h的最小点集的基数.交叉立方体网络是超立方体的一个变形,在平行计算系统当中交叉立方体是最重要的网络之一.该文证明了n维交叉立方体2-和3-限制性连通度分别是4n-8(n≥4)和8n-24(n≥5).     

一类Frobenius图网络

构造了一类有限域上向量空间加法群的凯莱图,它是对超立方体图的一种自然推广.证明了这类图是哈密尔顿连通和哈密尔顿可分解的、具有最大的点连通度而且既是超点也是超边连通的,因此它也是一个非常好的网络模型.更进一步,在某些条件下证明了它还是一类Frobenius图,因此这类图比一般的凯莱图对称性更强.     

排列图在PMC模型下的g好邻条件诊断度

诊断度是评估和判定多处理器计算机系统互连网络的自我故障诊断能力的重要指标。g好邻条件诊断度推广了经典的诊断度的概念,它要求每个非故障结点没有发生故障的邻点个数至少有g个。本文以PMC为模型,对排列图A_(n,k)的g好邻条件诊断度的上、下界进行讨论,最终得到了A_(n,k)在PMC模型下的g好邻条件诊断度为[(g+1)k-g](n-k).     

具有最佳连通性的12度与13度可靠连通网络

本文利用连通循环图及其连通度的有关理论,得到了关于连通循环图的原子部分的一些性质,并得出12,13度连通循环图的连通度等于其度数的充要条件,从而可构造具有最佳连通性的12,13度可靠连通网络。     

分层立方网络在MM~*模型下的g好邻条件诊断度

诊断度在衡量互联网络可靠性方面有着重要的作用。许多著名网络的诊断度已被研究。g好邻条件诊断度扩展了传统诊断度的概念,它要求每个非故障处理器至少有g个非故障邻点。本文证明了分层立方网络HCNn在MM*模型下的1-好邻条件诊断度为2n+1,2-好邻条件诊断度为4n-1.     

韧度变种与k-树的连通偶因子

连通偶[2,2s]-因子H是G的连通生成子图，且每个顶点在H中的度属于{2,4,…,2s}.韧度变种用于衡量网络的易受攻击程度，是网络拓扑设计的重要指标.给出图存在连通偶[2,2s]-因子的韧度变种条件，该结论在网络数据传输中有潜在的应用.     

一些可靠通讯网络的构造

本文首先得到了循环图的原子部分仍为连通循环图的结果,同时还得到了连通循环图的连通度的一些性质。然后应用这些结果与循环图的理论,得到了5,7,8,9度连通循环图的连通度等于其度数的充要条件,从而可构造出5,7,8,9度可靠通讯网络。     

循环图的代数连通度的下界

循环图是一类重要的网络拓扑图.图的拉普拉斯矩阵谱,特别是图的代数连通度,在与网络相关的广泛领域(包括与网络有关的动力问题)中发挥重要作用.本文中,利用循环图的特征值理论,研究了循环图的代数连通度的下界问题,得到了代数连通度的两个下界.     

超立方体Q_n在PMC模型下的2-条件诊断度

诊断度是衡量多处理器系统自我诊断能力的重要参数,是多处理器系统互连网络能够诊断出故障点的最大数。2-条件诊断度的概念是条件诊断度概念的一个推广,要求系统中的每个结点至少有2个好邻点。研究了超立方体Q_n在PMC模型下的2-条件诊断度并证明了Q_n在PMC模型下的2-条件诊断度为16n-57.