优化正则图的限制边连通性的最小度条件(英文)

限制边割将连通图分离成不含孤立点的不连通图 ,如果最小限制边割只能分离孤立边 ,则称图G是超级限制边连通的 .证明了如果k >|G|/ 2 +1,那么k正则连通图G是超级限制边连通的 ,k的下界在一定程度上是不可改进的 .

笛卡尔乘积图的超级3-限制边连通性

设Gi是一个极大边连通的k i-正则图,且k i≥3,i=1,2,证明了:如果围长g(G i)≥4,则其笛卡尔乘积图G1□G2是超级3-限制边连通的;同时提出了在特定条件下笛卡尔乘积图Gm□G和K 2□G是超级3-限制边连通的充要条件.

图是超级限制边连通的一个充分条件

图的超级限制边连通性是度量计算机互连网络可靠性(容错性)的一个重要参数。本文通过考虑图的超级限制边连通性,得到如下结论:若G是n(>7)阶不含三角形的图且对任一对不相邻的顶点x与y有d(x)+d(y) n-1,则G是超级限制边连通的,即super-λ′的。

超图的限制边连通度与最优限制边连通

设H=(V,F)是顶点集为V,超边集为E的连通超图。对H的边子集S,若H\S不连通而且不含孤立点,则称S是H的一个限制边割。把H中最小限制边割的基数称为H的限制边连通度,记为λ’(H)。对边e,其边度是指在H中与e相交的超边的数目,H中最小边度记为ξ(H)。如果λ’(H)=ξ(H),那么称超图H是最优限制边连通的,简记为λ’-最优。研究超图H的限制边连通度和λ’-最优,推广了图上关于限制边连通度和λ’-最优的一些结论。

图是λ_5-最优的邻域交条件

基于目前网络边连通性在网络拓扑性能方面的广泛应用和高阶限制边通图的各种邻域条件的广泛关注,针对图的高阶限制边连通性的最优化问题进行了深入的研究。该结论通过运用分类讨论和反证假设的方法,对前人一些已知的结果进行推广和改进,给出了阶为n的λ5-连通图的邻域交条件,从而得出图是λ5-最优的充分性条件。这些结论在大规模网络系统中度量网络性能的可靠性和容错性分析方面都有一定的应用,并对研究更高阶的网络连通性的最优化问题提供了方法和理论依据。