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

设 G是 n阶简单无向图 ,G的顶点 x的度记为 d(x) .证明了如果对 G中每一对不相邻的顶点 x和 y都有 d(x) +d(y)≥ n+2 ,那么 ,G是超级限制性边连通的 ,除非 n≥ 6是偶数且 G=2 Kn/2 ∪ F2 ,这里 F2 是 G的一个 2因子 .这一结果是对图的极大限制性边连通性的 Ore型充分条件的进一步扩展 .

半传递重图的限制性边连通度（英文）

设G=(V,E)是一个重图(包含重边,但不含环).图G的边连通度,记为λ(G),是G的最小边割的基数.我们称G是极大边连通的如果λ(G)=δ(G);称图G是超边连通的如果每个最小边割都是某个点的邻边集合.图G的限制性边连通度,记为λ(G),是图G的最小限制性边割的基数.如果λ(G)达到限制性边连通度的上界,我们称G是λ-最优的.一个二部重图是半传递的如果它作用在每个部分上都是传递的.在本文中,我们将刻画极大边连通的、超边连通的、λ-最优的半传递重图.

直径为2的图的超级边连通性质

Ｍ．Ａ．Ｆｉｏｌ在１９９２年给出了直径为２的无向简单图是超级边连通的三个充分条件（Ｆ１）、（Ｆ２）和（Ｆ３）．本文证明了：（１）条件（Ｆ１）也是必要条件，从而得到直径为２的图是超级边连通图的特征刻画；（２）（Ｆ３）（Ｆ２）（Ｆ１），但（Ｆ１）／（Ｆ２）／（Ｆ３）；（３）条件（Ｆ３）可进一步保证图是最优超级边连通的，但（Ｆ２）不能．这里的最优超级边连通的概念是通过限制性边连通度自然地定义的．最后提出两个有关的待解决的问题．

基于跳数约束的无向图R边连通扩充

提出了一个启发式迭代求解基于跳数约束的任意无向图R边连通扩充问题的算法.首先形成一个初始R边连通图,通过边交换和边替代来迭代降低扩充边集的费用,然后增加一些边满足跳数约束,再通过边置换和边删除来降低费用得到一个最优或较优的扩充图.给出了算例说明了算法的可行性.

极大限制边连通网络的充分条件

限制边连通度是度量网络可靠性的重要参数。设G是一个边集为E的连通网络。称一个边集合S?E是一个限制边割,如果G-S是不连通的且每个分支至少有两个顶点。网络G的限制边连通度,记为λ',定义为G的最小限制边割的基数。设d(v)表示顶点v的度,ξ=min{d(u)+d(v)-2:uv∈E}表示G的最小边度。称网络G是极大限制边连通的,如果λ'=ξ。给出了网络是极大限制边连通的一些充分条件。

极大3限制边连通图的充分条件

k限 制 边 连 通 度 是 度 量 网 络 可 靠 性 的 重 要 参 数。 设G = (V, E)是 一 个 连 通 网 络。 称 一 个 边 集 合S ? E 是一个k限制边割,如果G ? S的每个连通分支至少有k个顶点。 称G的所有k限制边 割中所含边数最少的边割的基数为G的k限制边连通度,记为λk (G)。 定义ξk (G) = min{[X, Y ]:|X| = k,G[X]连通,Y = V (G)\X}。 称网络G是极大k限制边连通的,如果λk (G) = ξk (G)。 给出了网络是极大3限制边连通的一些充分条件。

图是极大限制边连通的一个充分条件

设G是n阶简单无向连通图,G的限制边割是删除它以后G不连通,且留下的每个分支不含孤立点的边子集;限制边割的最小基数称为限制边连通度.记G的顶点x的度为d(x)。证明了若对超级连通图G中任意一对不相邻的顶点x和y都有d(x)+(dy)n,则G是极大限制边边通的当且仅当G不同构一种特殊图G。

有向图极大与超级局部边连通性的依赖团数的度序列条件

运用Turán定理,给出有向图的极大局部边连通性和超级局部边连通性的依赖团数的度序列条件。不同的例子将说明这些条件是最好可能的。

最大边连通和super-边连通超图的充分条件

设H是连通超图。若超图H的边连通度等于其最小度,则称H是最大边连通的。若超图H的每个最小边割总是由关联于某个最小度顶点的边集所构成,则称H是super-边连通的。首先给出一致线性超图是最大边连通超图的度序列条件。其次,给出一致线性超图是super-边连通超图的度条件。这些结果分别推广了D ankelmann和Volkmann(1997)以及Hellwig和Volkmann(2005)在图上的相关结论。

极大与超级局部边连通有向图的邻域条件

本文主要给出了有向图和二部有向图是极大局部边连通和超级局部边连通的邻域条件,不同的例子说明这些条件是最好可能的。

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

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

极小n边连通图的几个性质

设Ｇ是简单极小ｎ边连通图，最大度为△（Ｇ），ｎ度顶点集合为Ｄ．对每一顶点ｘ∈Ｖ（Ｇ），给出Ｖ（Ｇ）─（Ｘ）一个特殊划分，并由此推出｜Ｄ｜≥△（Ｇ）及存在ｄ（ｘ）条边不相交的Ｘ－Ｄ路．

围长为g>5的极大4限制边连通图的充分条件

设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λk(G).定义ζk(G)=min{[X,Y]:|X|=k,G[X]连通,Y=V(G)\X}.称图G是极大k限制边连通的,如果λk(G)=ζk(G).本文给出了围长为g>5的极大4限制边连通图的充分条件.

极大4限制边连通图的充分条件

设G=(V,E)是一个连通图。称一个边集合S⊆E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点。称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λk(G)。给出了图是极大4限制边连通的充分条件。

任意无向图的最小R边连通扩充

研究了以最少边集扩充一个任意无向图为R边连通图这一优化问题。给出了一个复杂度为O(|V|~5)的算法。利用该算法可最优地将所研究图形中任意两点达到所要求的边连通度。它发展了K边连通最优扩充的研究,从而使图的边连通扩充的研究在应用于网络结线的可靠性设计方面更具有实际意义。

补图为2-点或2-边连通的图的最小特征值(英文)

图的最小特征值定义为图的邻接矩阵的最小特征值,是刻画图结构性质的一个重要代数参数.在所有给定阶数的补图为2-点或2-边连通的图中,刻画了最小特征值达到极小的唯一图,并给出了这类图最小特征值的下界.

任意有向图的最小K边连通扩充

本文研究了以最小边集扩充一个任意有向图为K边连通有向图这一优化问题。提出了一个复杂度o(|V|5)的有效算法。该算法为可靠网络的计算机辅助设计打下了基础。

变换图G^(-+-)的极大边连通性

对任意图G=(V(G),E(G)),其变换图G^(-+-)的顶点集为V(G)∪E(G),顶点α和β在G^(-+-)中邻接当且仅当下列条件之一成立:当{α,β}■E(G)时,α和β在G中不邻接或不关联;当{α,β}■ E(G),α和β在G中邻接。证明了所有连通的变换图G^(-+-)都是极大边连通图。

基于跳数约束的R边连通网络设计

基于跳数约束的R边连通网络设计就是设计一个网络,且任意两点之间满足给定的边连通度及跳数要求,使得链路的总费用为最小。本文提出了一个启发式迭代求解该问题的算法。首先形成一个初始R边连通图,通过边交换来迭代降低边集的费用;最后增加一些边满足跳数约束,再通过边置换和边删除来降低费用得到一个较优的扩充图。

极大局部边连通有向图的度条件

对有向图D=（V（D），E（D）），顶点u和v的局部边连通度λ（u，v）=min{｜X｜：X真包含E（D），D—X中不存在从u到v的路}．若对D中任意两个顶点u和v，λ（u，v）=min{d^＋（u），d^-（v）}，称D为极大局部边连通的．笔者得到了有向图是极大局部边连通的两个度条件，推广了别人的三个结果．