图的围长与k-联性

联性是图的一个重要的连通性质，Kawarabayashi证明了对k≠4，5，围长至少为11的2k-连通图是k-联图．本文对该结果进行了改进，证明了对k≥12，围长为9，或7≤k≤11，围长至少为10的2k-连通图是k-联图．     

k连通图在边点割原子与点割上的可去边

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割断片的性质给出某些k连通图中在特定子图上可去边的分布情况,得到了最小度至少为(3(k-1)/2)或围长至少为4的k连通图(k≥4)中由边点割原子与点割所导出的子图的每一条边都是可去边.     

正则图m-限制边连通度的存在性

图G的m-限制边割是删除它以后G不连通,且留下的每个分支的阶至少为m的边子集;m-限制边割的最小基数称为m-限制边连通度。设G是连通（k-2）-正则图,阶至少为2k（k≥5）。证明了G的k-限制边连通度存在当且仅当G不属于一种特殊图类G^＊ k-2.     

判断k-可序哈密顿-连通图的新条件

具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图.     

无爪图的周长

证明了如果G是k-连通的非Hamilton无爪图,k≥2,则G包含一个长度至少为：min{∑x∈Xd（X）＋2k：X是G的独立集,｜X｜=k}的圈。     

k阶限制边连通度最优的一个充分条件

设S是图G的一个边子集,若G-S不连通且每个分支的阶至少为k,则称S为G的一个k-限制边割.若G有k-限制连割,G的最小k-限制边割的边数称为G的k阶限制边连通度,记为λk(G).记ξk(G)=min{|[X,]|∶|X|=k,G|X|连通},若λk(G)=ξk(G),则称G是λK-最优的.证明了若对G中任意一对不相邻的顶点x,y都有d(x) d(y)≥n 2(k-2),且G不是G*k图,则G是λk-最优的.     

k-连通图中最长圈上可收缩边的数目

给出了k-连通图中最长圈上的可收缩边的数目,得到如下结果:任意断片的阶至少为「k/2+1 的k-连通图中最长圈上至少有3 条可收缩边;更进一步,若该k-连通图中存在哈密顿圈,则哈密顿圈上至少有6 条可收缩边。     

正则2-连通图的最长圈

P.Erdos和A M Hobbs在[1]中提出如下的结论:设k≥6,G是2k个顶点的(k-2)次正则的2-连通图,则G是Hamilton图(以下简称为H图)。本文提出比上述结论更为广泛的定理:定理1 设k≥4,G是n个顶点的(k-2)次正则的2-连通图,则除G是peterson图外,G必有个长至少为min{n,2k}的圈。由于:(i)定理1中的k=4时,G是2-正则2-连通图,G是H图,它有个长为n≥min{n,2k}的圈;(ii)定理1中的k≥5且n≤3(k-2)时,根据[2]中的B.Jackson定理知,这时G是H图,它有个长为n≥min{n,2k}的圈。因此,要证明定理1成立,只要证明如下的定理2成立。定理2 设n≥3k-5≥2k,G是n个顶点的(k-2)次正则的2-连通图,则除G是Peterson图外,G必有个长至少为2k的圈。在证明定理2的过程中,本文作下列的假设:     

混合图的双向连通定向

无向图的双向连通定向对单行道路系统的构造有着重要意义。本文讨论的问题实际上是无向图的双向连通定向问题的一种推广。本文主要结果有:1.设 B 为混合图 M 的任一 k-断集,则 M 有双向连通定向的充要条件为 M 是混合连通且 k≥2。2.设图 M 有混合 Euler-迹,又 M 中任一断集 B 有|B|≥2k,则 M 有一个 k-弧连通定向。3.设无环图 M 为混合连通,又(?)b∈E(M)∪A(M),有 M-b 为混合连通,则 M 的 DFS-图是双向连通。     

混合图的双向连通定向

无向图的双向连通定向对单行道路系统的构造有着重要意义。本文讨论的问题实际上是无向图的双向连通定向问题的一种推广。本文主要结果有:1.设 B 为混合图 M 的任一 k-断集,则 M 有双向连通定向的充要条件为 M 是混合连通且 k≥2。2.设图 M 有混合 Euler-迹,又 M 中任一断集 B 有|B|≥2k,则 M 有一个 k-弧连通定向。3.设无环图 M 为混台连通,又 b∈E(M)∪A(M),有 M-b 为混合连通,则 M 的 DFS-图是双向连通。