λ_(3,q)-连通图的刻画(英文)

连通图G称为λ3,q-连通的如果存在边割S使得G-S有两个阶数分别至少为p和q的连通分支。给出一个图是λ3,q-连通的一些充分和必要条件。     

λ3,q-连通图的刻画

连通图G称为λ3,q-连通的如果存在边割S使得G-S有两个阶数分别至少为p和q的连通分支。给出一个图是λ3,q-连通的一些充分和必要条件。     

图与补图孤立断裂度的关系

连通图G的孤立断裂度isc(G)=max{i(G-S)-｜ S ｜:S∈C(G)},其中i(G-S)是G-S中的孤立点数,C(G)是G的点割集.文章研究了图与补图孤立断裂度的关系.     

λ′-最优图的充分条件

设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是λ′-最优的.对于不含钻石的图也得到了类似的结果.     

自补图的L(2,1)-标号

研究自补图G的L（2，1）-标号问题，证明了自补图的L（2，1）-标号数满足λ（G）≤2△。验证了关于一般图的L（2，1）-标号数的猜想λ（G）≤△2对于自补图的正确性。     

2-重自补图和有向自补图的几个性质

本文讨论了2-重自补图和有向自补图的连通性以及2-重自补图的直径,同时以自补置换作为工具研究了当2-重自补图或有向自补图被分成两个连通分支后,这两个连通分支之间的边数与顶点数之间的关系.     

路的k阶幂图的连通性研究

设G是连通图,G的k阶幂图G^k是一个与G具有相同顶点集的图,G^k中的两个顶点相邻当且仅当这两个顶点在G中的距离不大于k.本文研究了路的幂图P_n^k的点连通度κ(P_n^k)、边连通度λ(P_n^k)和限制边连通度λ₂(P_n^k).得到：当n>k时,κ(P_n^k)=λ(P_n^k)=k;关于限制边连通度：当2≤n≤k+1时λ₂(P_n^k)=2n-4,当n>k+1时,λ₂(P_n^k)=2k-1.     

折叠交叉超立方体的2-额外连通度和2-额外边连通度

有各种各样的方法去衡量不同网络的可靠性和容错性.一个连通图G的g-额外连通度Kg(g-额外边连通度λg)是顶点数最小的顶点集S(边数最少的边集S),使得G-S不连通,并且剩下的每个连通分支含有的顶点数至少是g+1.探究n-维折叠交叉超立方体FCQn的2-额外连通度和2-额外边连通度,证明得到如下结论:当n≥8时,κ2(...     

一类图的色等价图类

设G是一个图,P（G,λ）是G的色多项式,用[G]p表示以P（G,λ）为其色多项式的所有图的集合,称为图G的色等价类.刻画了[I^cm]p,其中Im（m≥6）表示路Pm-4的两个端点分别粘接一个^＋P3的2度点后得到的图.G^c表示G的补图.     

图与其补图的独立数之间的关系

文章讨论了图G及其补图(?)的独立数之间的关系,得到的主要结果是a(G) a((?))(?)n 1.     

非连通图(P1∨Pn)∪Gr和(P1∨Pn)∪(P3∨r)及Wn∪St(m)的优美性

讨论非连通图((P₁∨P_n)∪G_r和(P₁∨P_n)∪(P₃∨_r)及W_n∪St(m)的优美性, 证明了如下结论： 设n,m为任意正整数, s=［n/2］, r=s-1, G_r是任意具有r条边的优美图, 则当n≥4时, 非连通图((P₁∨P_n)∪G_r和(P₁∨P_n)∪(P₃∨_r)是优美图； 当n≥3, m≥s时, 非连通图W_n∪St(m)是优美图. 其中, P_n是n个顶点的路, K_n是n个顶点的完全图, n是K_n的补图, G₁∨G₂是图G₁与G₂的联图, W_n是n+1个顶点的轮图, St(m)是m+1个顶点的星形树.     

线图及复合图的边完整度

图G的边完整度定义为I'(G)＝minS包含E{|S| m(G-S)}，被用来衡量网络特别是通讯网络的脆弱度，它刻画了破坏网络的难易程度和网络遭受破坏的程度．论文主要给出了线图、复合图的边完整度及图的边完整度和其线图的完整度之间的关系．     

围长为4的无7-,8-圈和15-圈平面图的3-选色

图G的选色数(记为χ_l(G)), 定义为最小的自然数k, 满足当对任一顶点给定k种颜色的列表, 且染色时每个顶点的颜色只能从自身的颜色列表 中选择时, 存在图G顶点的一个正常着色. 应用Discharging方法对上述问题进行研究, 证明了每个围长至少为4且不含7-圈, 8-圈和15-圈的平面图是3-可选择的.     

孤立断裂度给定条件下的一类图

连通图G的孤立断裂度isc（G）=max{i（G-S）-｜S｜：S∈C（G）},其中C（G）是G的点割集,i（G-S）是G-S中的孤立点数.文章给出了顶点数和孤立断裂度为定值的具有最大边数和最小边数的连通图.     

几类并图的优美标号

 对非连通并图的优美性进行了研究,给出了几类非连通的并图,得出了如下结果：对任意的正整数n,m,设s是不超过n/2的最大整数,P_n是n个顶点的路,St(m)是m+1个顶点的星形树,路P₂的补图与路P_n的联图记为A_n,则当n≥2时,A_2n与任意一个具有n-1条边的优美图的并图是一个优美图;当n≥5,m≥s+2时,A_n与星形树St(m)的并图是一个优美图,从而A_n与星形树St(n)的并图是一个优美图;当n≥5时,A_n与任意一条路P_n的并图是一个(n－s)-优美图。     

简单图的L(2,1,1)-标号

给出了完全图、完全二分图、路、圈等简单图的L(2,1,1)-标号数。对最大度为Δ 的一般图G,给出了构造L(2,1,1)-标号的一个算法, 证明了λ_2,1,1(G)≤Δ³- Δ²+2Δ。     

(a,b,Ck) 临界图

设G是一个图且a,b是非负整数,a≤b。给出了图G是(a,b,Ck) 临界图的一个充分必要条件,讨论了该条件的一些应用,研究了(a,b,Ck) 临界图与联结数的关系。     

一类正则图的邻强边染色

研究一类正则图G(n,n,r)(n=1,2(mod 3))的邻强边染色. 用构造性方法给出了一类正则图的邻强边染色, 验证了对|V(G)|≥3的连通图G（V,E）(G(V,E)≠C₅), 有Δ(G)≤χ′_αs(G)≤Δ(G)+2成立.     

几类图的均匀邻点可区别全染色

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设G（V,E）为一个简单图,f为G的一个k-邻点可区别全染色,若f满足||Vi∪Ei|－|Vj∪Ej||≤1（i≠j）,其中,Vi∪Ei={v|f（v）=i}∪{e|f（e）=i},记C（i）=Vi∪Ei,则称f为G的k-均匀邻点可区别全染色,简记为k-EAVDTC,并称χeat（G）=min{k|G存在k－均匀邻点可区别全染色}为G的均匀邻点可区别全染色数。本文给出了路、圈、风车图K t 3、图Dm,4和齿轮图■n的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。