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

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

正则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-图是双向连通。     

关于最大的极小k—连通图的构造

本文讨论了如何对已知的 k=k(G)构造一个 n 阶的具有最多边数的极小 k—连通图,同时得出了极小 k—连通图的边数的上界.如果 k 1相似文献   

任意连通图与偏k-树乘积图的树宽

一个图的树宽是使图成为一个k-树的子图的最小整数k,本文考虑了顶点数为m的任意连通图C与顶点数为n的k-连通的偏k-树的乘积图的树宽,首先利用对已知结构图进行树分解的方法,确定了二者乘积图树宽下界,然后结合乘积图树宽的上界,得出了在满足顶点数n≥mk的条件下二者乘积图树宽表达式.     

判断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-可序哈密顿-连通图.     

k—连通图为Dλ—连通的一个充分条件

本文在对有限简单图给出 D_λ—连通的定义之后,证明了下述定理:设 G 是n 阶 k—连通(k≥3)的有限简单图,如果对任意的 Y∈I_k(G,λ),有sum from i=1 to k (k+i-2)/(k-1)s_i(Y、λ)>n-k(λ-1),则 G 是 D_λ—连通的.     

有向笛卡尔积图的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-联性

k-联性是图的一个重要的连通性质.Kawarabwyshi证明了对每一个k≠4,5,围长至少为11的2k-连通图是k-联的.主要证明:当k≥46时,每一个偶围长至少为8的2k-连通图是k-联图.     

图的修正的k-顶点彩虹连通度

路P称为图G的修正的顶点彩虹路,如果P中所有的顶点着不同的颜色或者除端点外其余内部顶点着不同于端点的颜色且内部顶点染色各不相同.图G称为是修正的k-顶点彩虹连通的,如果对于G的任意两个顶点u和v,G都有k条内部不交的修正的顶点彩虹u-v路.使得图G是修正的k-顶点彩虹连通图的最小颜色数目k称为图G的修正的k-顶点连通度,记做rvc*k(G).文中给出了C_n,W_n,K_(p,q)和K_n的修正的k-顶点彩虹连通度.     

具有次最小阶的连通的残差完备图

讨论连通的残差完备图,确定了连通的K2残差图的第二个最小阶及n≠2时,连通的Kn残差图的次最小阶,即min{v(G)|G是连通的Kn残差图,v(G)>2n 2}=2n 3,n=2,4,62n 4,n≠2,4,6并且构造了对应的残差完备图;同时证明了n=6时,C5[K3]是唯一的2n 3阶的连通Kn残差图,还对任意正整数n和k,构造了具有2n 2k阶的残差完备图.     

k-连通半无爪图的Hamilton性质

半无爪图是包含无爪图的更大的图类。关于k-连通半无爪图,得到以下结果:G是k-连通的半无爪图(k≥2),如果对于G2的任意基数为k 1的独立集X,都有∑d(v)≥n-k,则G是Hamilton图。     

非连通图G+e∪H_(k-1)的优美性

证明了当k≥2时,非连通图G+e∪Hk-1是优美图,其中G是特征为k的平衡二分图,Hk-1是任意一个k-1条边的优美图.     

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

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

关于图连通k-控制数的若干结果

设G为连通图，γ‘‘k(G)表示G的连通k-控制数，讨论了γ‘‘k(G)的上下界，并证明了γ‘‘k(G)≤(2k k 1/2)irk(G)-2k，其中irk(G)是图G的k-无赘数．     

k-连通[k+3,k]-图中的Hamilton路

如果G的任意s个点的导出子圈中至少含有t条边,则称图G为[s,t]-图.本文证明了若G是k-连通[k+3,k]-图(k≥2),则G或者含有Hamilton路或者同构于Kk+2∨ Gk(其中Gk是含有k个点的任意图).     

一类特殊图k-限制边连通度

设F?E (G)为图G=(V,E)的一个边集,如果G-F不连通且G-F的每一个连通分支都至少有k个顶点,F就称为图G的一个k-限制性边割.图G的k-限制边连通度是图G的最小k-限制性边割的基数,记为λk(G).限制性边连通度是衡量网络可靠性的重要参数之一.证明了在2≤k≤n,h≤n/2的情况下,一类特殊图—蜻蜓网络D(n,h)的k-限制边连通度是■     

(s,k)-连通图

图G为（s,k）-连通图,如果G中任意s个顶点的导出子图是k-连通的。证明了：如果s-k≤｜G｜-1/2,则（s,k）-连通图G是完全圈可扩的。由此推出,若图G的连通度κ（G）≥｜G｜＋1/2,则G是完全圈可扩的。     

图的围长与k-联性

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