竞赛图中的泛连通性点对

证明了每个连通的但非强连通的竞赛图中至少存在一个泛连通性点对且该点对可在多项式时间内找到。另外,我们还得到连通的但非强连通的竞赛图中存在泛连通性点对的个数。特别地,证明了每个连通的但非强连通的竞赛图中不存在恰好两个泛连通性点对。

完全二部图K_(n,n)的容错偶泛连通性和完全k(k≥3)部图K_(n,n,…,n)的泛连通性

图G称为泛连通的,如果对于G中距离为d(x,y)的任意两点x和y,G中都存在每个长为l的x:y路(这里d(x,y)≤l≤︱V(G)︱-1);图G称为偶泛连通的,如果对于G中距离为d(x,y)的任意两点x和y,G中都存在每个长为l的x: y路(这里d(x,y)≤l≤︱V(G)︱-1),且l和d(x,y)有相同的奇偶性.本文用归纳法证明了以下结论:当n≥2时,在完全二部图K n,n中,若故障边数︱Fe︱≤n-2,则K n,n-Fe是偶泛连通的,并且︱Fe︱的上界n-2是最优的;完全k(k≥3)部图K n,n,…,n是泛连通的.

单位区间图的泛连通性

证明了顶点数至少是4的单位区间图是泛连通的当且仅当它是3-连通的。

泛圈性、泛连通性和哈密尔顿性的一些重要结果的统一及改进

设ｘ，ｙ为满足ｄ（ｘ，ｙ）= ２的任意两点，研究了ｄ（ｘ）＋ｄ（ｙ）≥ｎ＋１条件下的ｎ阶图Ｇ的泛连通性，改进或推广了文献［１～３］的结果。

扩张竞赛图中的泛连通性点对

研究了扩张竞赛图中的泛连通性点对的存在性问题。证明了如果传递的扩张竞赛图D不是竞赛图,那么D中不包含泛连通性点对。研究了扩张竞赛图中存在泛连通性点对的充分条件:证明了(a)设D1,D2,…,D t是连通但非强连通的扩张竞赛图D的一个强分支无圈序。若D i(i=1,2,…,t)有1-路-圈因子,则D中必存在泛连通性点对。并且找到泛连通性点对的时间复杂度为O(n2.5).(b)设D是由连通但非强连通竞赛图T的强分支T i(|V(T i)|≥3)平衡扩张而成的,(当|V(T i)|=1时,T i不变),则D中必存在泛连通性点对。

距离为2的邻集并条件与图的泛连通性(英文)

设G是一个顶点数为n(≥5)最小度为δ的2-连通简单图．本文证明了若图G的每一对距离为2的顶点u,v都满足|N(u)∪(v)|≥n-δ+1,则除非G属于某些特殊图类,它的任意一对顶点x,y之间都存在长度从d(x,y)到n-1的路．

有关加强超立方体泛连通性的证明

在本论文中,我们研究容错加强超立方体Qn,k中的路和圈的嵌入问题.我们利用已知的结论当n(≥3)和k有相同奇偶性时,Qn,k-{f}包含一个长为4到2n-2容错偶泛圈;进一步地,我们证得当n和k有相同奇偶性时,Qn,k(1≤k≤n-1)是偶泛连通的.

有关加强超立方体泛连通性的证明

在本文中，我们研究容错加强超立方体Qn，k中的路和圈的嵌入问题。利用已知的结论当n（≥2）和k有不同奇偶性时，,Qn k-{f}包含了长从4到2n-2容错偶泛圈和长从n-k＋2到2n-1的容错奇泛圈；当n和k有不同奇偶性时Qn，k（1≤k≤n-1）是哈密顿连通的。

关于图的泛连通性的几个结果

如果对ａ≤ｉ≤ｂ，图Ｇ的任一对顶点ｕ、ｖ都存在长为ｉ－１的路Ｐｉ（ｕ，ｖ），则称Ｇ是［ａｂ］－泛连通的．文中证明了关于图的泛连通性的下述结果：设Ｇ为ｎ阶连通图，且对Ｇ中任一对距离为２的顶点ｕ，ｖ，有ｄ（ｕ）＋ｄ（ｖ）≥ｎ，则图Ｇ是［５ｎ］－泛连通的当且仅当Ｇ是Ｈ连通的．此结果推广了Ｆａｕｄｒｅｅ和Ｓｃｈｅｌｐ的一个结论．

生成子图与图的泛路连通性

本文讨论了图的泛路连通性,提出并证明了几乎泛路连通图的两个充分条件。

超立方体网络的边容错二部泛连通度(英文)

证明了对于至多有n-1条故障边的容错超立方体网络Qn,如果它正好有n-1条故障边但不关联于同一个顶点,那么对于Qn中任意两点u和v,存在一条长为l的uv非故障路,路长l满足dQn(u,v)+2≤l≤2n-1且2|(l-dQn(u,v)).这改进了许多已知结果.

一类偶图的顶点——[6,2n]泛偶圈性

一个阶数为2n的偶图G中每个顶点均有长为2k(l≤k≤m)的圈通过,则称G是顶点——[2l,2m]泛偶圈的。作者在文献[3]中证明了如下结果: 设G=(X,Y,E)是一个2n阶连通偶图。如果G中任意一对距离为3的顶点的次数之和不小于n+1,则G中有长为4,6,8,……,2n的圈。除非G是长为6的圈。本文从连通性出发,证明了满足上述条件的图G是顶点——[6,2n]泛偶圈的。深化了上述结果。

变形超立方体的圈和路嵌入(英文)

作为超立方体网络Qn的变形,n维变形超立方体VQn具有许多优于超立方体所具有的性质.这里证明了对任何整数l∈[4,2n],VQn中每条边被包含在长度为l的圈中除非l=5;对任何顶点对(x,y)和整数l∈[d,2n-1],其中,d为这两点之间的距离,VQn中存在长度为l的xy路除非当d=1时l=2,4.