极大3等周边连通图的充分条件

k等周边连通度是一个比边连通度更可靠的网络可靠性参数。 连通图G的k等周边连通度定义为γk(G)=min{［X,X-］:XV(G),X≥k,X-≥k},其中X-=V(G)＼X。令βk(G)=min{［X,X-］:XV(G),X=k}。图G是极大k等周边连通的如果γk(G)=βk(G)。令G是一个阶至少为6的连通图。本文证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N(u)∩N(v)≥2;当u和v中至少有一个在三角形中时满足N(u)∩N(v)≥5,那么G是极大3等周边连通的。     

λ5-最优图的一个充分条件

设G是一个λ5-连通图,定义ξ5(G)=min{|[X,X]|:X■V(G),|X|=5,G[X]是连通子图},若λ5(G)=ξ5(G),则称G是λ5-最优图.文章给出了满足顶点数v≥17且最小度δ≥v/2-4的λ5-连通图G在一定特殊条件下是λ5-最优图的一个充分条件.     

5等周边连通图的邻域条件

文章研究了5等周边连通图的领域条件,若G是一个阶至少为10的连通图,对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足|N(u)∩N(v)|≥4;当u和v中至少有一个在三角形中时满足|N(u)∩N(v)|≥9,则G是γ_5-最优的.     

图是λ_k-最优的和超级-λ_k的度条件

设S是连通图G中的一个边子集。若G-S不连通且它的每个连通分支的阶至少为k,则称S是G的一个k限制边割。图G的最小k限制边割的边数称为G的k限制边连通度,记为λk(G).义ζk(G)=min{|[X,X]|∶|X|=k,G[X]连通},其中X=V(G)\X.若λk(G)=ζk(G),则称G是λk-最优的。如果图G的每个最小k限制边割都孤立了一个k阶连通子图,那么称G是超级-λk的。设k是一个不小于2的正整数且G是一个阶不小于2庇的图。本文证明了若对于G中任意一对不相邻顶点u,v都有d(u)+d(v)≥ν+2k-4且G不属于一类特殊图,则G是λk-最优的。最后,给出了图是超级-λk的一个充分条件。     

λ5-最优图的邻域交条件

给出了λ5-最优图的邻域交条件:设G是一个阶至少为10的连通图,对G中任意一对不相邻顶点u和v,若u,v均不在三角形中,有|N(u)∩N(v)|≥6,若u或v在三角形中,有|N(u)∩N(v)|≥9,则G是λ5-最优的;若G中任意一对不相邻顶点u和v满足|N(u)∩N(v)|≥7,任意一条边xy满足|N(x)∩N(y)|≤3,则G是λ5-最优的.     

极大等周边连通图的一个邻域条件

图的等周边连通度是图的边连通度概念的推广,通过考察图中顶点的κ阶子图之间的关系,给出一个图是极大κ阶等周边连通的一个充分条件:设κ≥2是一个整数,G是一个阶至少为2κ的图,如果对G中任意两个不相邻的顶点u和v,有|N(u)∩N(v)|≥2κ-2,进一步,如果这两个顶点中至少有一个是某三角形的顶点,有|N(u)∩(v)|≥2k-2,进一步,如果这两个顶占中至少有一个是某三角形的顶点,有|N(u)∩N(v)|≥2κ-1,那么图G是rk最优的.     

λ′-最优图的充分条件

设G=(V,E)是一个连通图.边集SE,如果G-S不连通且G-S的每个连通分支至少有2个点,则称S是一个限制性边割.限制性边连通度λ′(G)就是G的最小限制性边割的基数.如果限制性边割存在,则称G是λ′-连通的.如果λ′(G)=ξ(G),则G是λ′-最优或者极大限制性边连通的,其中ξ(G)=min{|[X,Y]|:XV,|X|=2,G[X]连通}.图G的逆度是指R(G)=∑_v∈V 1/d(v).在此基础上,主要得到了:如果G是λ′-连通围长大于等于5的n阶图,且δ(G)≥2,如果R(G)小于某个关于最小度和顶点数的值,则G是λ′-最优的.对于不含钻石的图也得到了类似的结果.     

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

设S是连通图G中的一个边子集。若G S不连通且它的每个连通分支的阶至少为k,则称S是G的一个k限制边割。图G的最小k限制边割的边数称为G的k限制边连通度,记为λκ(G)。定义ξκ(G)=min{|［X,X］|:|X|=k,G［X］连通},其中X=V(G)＼X。若λk (G)=ξk(G),则称G是极大k限制边连通的。设G是一个围长至少为5的λ3 连通图。本文证明了若G中不存在5个点u1,u2,v1,v2,v3使得d(ui,vj)≥3(i=1,2;j=1,2,3),则G是极大3限制边连通的。     

图的λ_4-最优性的邻域交条件

本文给出了图的λ4-最优性的邻域交条件:设图G是阶数大于等于11的λ4-连通图,对G的任意一对不相邻顶点u,v,若u,v均不在三角形中,有|N(u)∩N(v)|≥5,若u或v在三角形中,有|N(u)∩N(v)|≥7,则G是λ4-最优的;若G中任意一对不相邻顶点u,v满足|N(u)∩N(v)|≥5,任意一条边xy满足|N(x)∩N(y)|≤2,则G也是λ4-最优的.这些结果在网络可靠性分析中有一定应用.     

长圈的邻域并条件的推广

本文证明了若G为一个k(k≥2)连通简单图,最小度为,δV(G)=n≥3,X 1,X 2,……,X k是顶点集合V的子集,X=X1∪X2∪…∪Xk,且对于Xi(i=1,2……k)中任意两个不相邻点u,v,都有N(u)∪N(v)≥n-δ,则X在G中可圈。并给出几个相关推论.     

可迹、邻域并和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)＝V(G),E(G*)＝E(G)∪{uv;uv∈E(G),且J(v,v)≠φ},这里J(u,v)＝{w∈N(u)∩N(v)N(w)∪N[u]∪N[v]}.本文利用插点方法,得到k-连通图(k≥1)是可迹的两个新的充分条件.     

图的λ_6-最优性的领域交条件

文章给出了满足一定条件的图的λ6-最优性的领域交条件.设图G是连通图,若对G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥10且｜X5｜≤5,则G是λ6-最优的;若对于连通图G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥10且对图中每个三角形T至少存在一个顶点v∈V（T）使得d（v）≥v2＋5,则G是λ6-最优的.     

2-连通图的最长圈

设G是2-连通图,λ(G)=min{d(u)+d(v)|u,v∈V(G),uv■E(G)},本文证明了除六类图外,G中最长圈的长c(G)≥min{|v(G)|,λ+2}。     

2-连通图过指定边的长圈

对2-连通非完全图G，令μ(G)=min{max{dG(v)}|dG(u,v)=2}．一个著名的范定理;每一个2-连通非完全图G包含长至少为min{|V(G)|，2μ(G)}的圈．在这篇论文中我们证明了：若G是2-连通无三角形图，则通过G的任一边存在长至少为min{|V(G)|，2μ(G)}的圈．     

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-最优的.     

关于图的哈密尔顿性的一些新的结果

关于哈密尔顿图和哈密尔顿连通的两个基本结果是Ore给出的:设G是一个n(n≥3)阶图,如果对于G的任意一对不相邻顶点u,v,有d(u) d(v)≥n或n 1,则G是哈密尔顿图或哈密尔顿连通的.设G是一个图,对于任意u∈V(G),令N(u)表示u的邻点集;对于任意U∈V(G),令N(U)=∪u∈UN(u).本文利用插点方法,给出了关于k或(k 1)-连通图(k≥2)G是哈密尔顿的,哈密尔顿连通的或1-哈密尔顿的统一证明.其充分条件是关于|N(S)| |N(T)|与n(S ∪T)的不等式,这里S,T是图G的任意两个不交的独立集,并且|S|=s,|T|=1,S∪T也是一个独立集,这里n(S∪T)=|{v∈V(G):dist(v,S∪T)≤2}|.     

泡序图的广义4-连通度

S?V(G)是G的一个顶点集且|S|≥k,其中2≤k≤n.连接S的树T叫作斯坦纳树.两棵斯坦纳树T₁和T₂称为内部不交的,当且仅当它们满足E(T₁)∩E(T₂)=?和V(T₁)∩V(T₂)=S.令κ_G(S)是G内部不交的斯坦纳树的最大数目,κ_k(G)=min{κ_G(S)∶S?V(G),|S|=k}定义为G的广义k-连通度.很显然,当|S|=2时,广义2-连通度κ₂(G)就是经典连通度κ(G).因此广义连通度是经典连通度的推广.主要讨论泡序图B_n的广义4-连通度κ₄(B_n).得到的结论是当n≥3时,κ₄(B_n)=n-2.     

泛圈图的一个新的充分条件

设G是一个阶为n的2－连通简单图,αv表示G中包含点v的最大独立集的点数,对任意uv不属于E,设Tuv=V\(N(u)∪N（v)),αuv=min{αu,αv}。本文证明了：如果对于任一对不相邻点u,v,｜N（u)∩N(v)｜≥min{αuv-1,｜Tuv｜},则除了一些特殊图外,对于G的任一点x和任意整数k(4≤k≤n),G包含长度为k县包含点x的圈。     

图的λ4-最优性的邻域交条件

文章给出了图的λ4-最优性的邻域交条件.设图G是阶至少为34的λ4-连通图,若对G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥6且ξ4（G）≤3n（G）/2＋3,则G是λ4-最优的;若对于λ4-连通图G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥6且对图中每个三角形T至少存在一个顶点v∈V（T）...     

完全对换图的广义3-连通度（英文）

令S■V(G)κ.G(S)表示图G中内部不交的S-树T1,T2,…,Tr的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(Ti)∩V(Tj)=S,E(Ti)∩E(Tj)=.定义κk(G)=min{κG(S)|S■V(G),且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.完全对换图在网络中是重要的一类Cayley图.该文证明了n-维完全对换图CTn的广义3-连通度是n(n-1)/2-1,也就是说,对于CTn的任意三个点,存在n(n-1)/2-1个连接它们的内部不交的树.