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

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

kp,q（G）≤λp,p（G）成立的一些充分条件

设G是简单有限无向连通图,p,q是两个正整数.G的一个边割(顶点割)S是一个p-q-边割(p-q-顶点割),如果G-S不连通,且G-S中有一个分支至少含有p个顶点,另一个分支至少含有q个顶点.G称为λp,q-(kp,q-)连通的,如果一个p-q-边割(p-q-)顶点割存在.用λp,q(G)(kp,q(G))表示最小p-q-边割(p-q-顶点割)的基数.文章证明了在kp,q-连通(p≤q)和λp,p-连通图G中,使kp,q(G)≤λp,p(G)成立的一些充分条件及k1.p-连通图的一些性质.     

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_λ—连通的.     

高度平面图的L(p,q)—标号

研究高度平面图G的L(p,q)-标号问题，证明了高度平面图h1-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+6(p-q)；h2-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+8p-6q-1. 对于L(2,1)标号问题Griggs和Yeh有一著名猜想：对最大度为Δ的任意图有λ(G)Δ2. 此猜想对高度平面图是正确的.     

无向广义De Bruijn图的m-限制边连通性

m-限制边割将连通图G分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图G的m-限制边通度,记作λm（G）.对于包含m-限制边割的连通图G,有λm（G）≤ξm（G）（m≤3）;如果λm（G）=ξm（G）,则称图G是极大m-限制边连通的.本文证明：当n≥7时,无向广义De Bruijn图UBG（2,n）是极大m-限制边连通的（m={2,3}）.     

线图的限制性邻域连通度

在间谍工作中,限制性边邻域连通度和限制性邻域连通度比一般连通度和边连通度更加稳定可靠。文中提出了两个新概念:限制性邻域连通度和限制性边邻域连通度。证明了如果图G的线图L(G)是κ’NC图,那么κRNC(L(G))=λRNC(G)当且仅当G不是super-λRNC。并且证明了如果G是λpN C+1,q+1(G)连通图,那么L(G)是κpN,Cq连通的,并且κpN,Cq(L(G))=λpN C+1,q+1(G)。     

Rota-Baxter q-3-李代数

定义q-3-李代数的权为λ的Rota-Baxter算子, 给出P为q-3-李代数权为λ的Rota-Baxter算子的充要条件, 并通过Rota-Baxter李代数、 Rota-Baxter结合代数、Rota-Baxter左对称代数和Rota-Baxter群代数等实现了Rota-Baxter q-3-李代数.     

点可迁图的限制边连通度

对于度k( ≥ 2 )的点可迁连通图的限制边连通度λ′,已知k≤λ′≤ 2k- 2 ,且λ′的界可以达到 .在此基础上 ,对度为k的点可迁图G进一步给出了满足λ′(G) =k的两个充要条件 .接着 ,对任意的连通图G0 证明了λ′(K2 ×G0 ) =min{2δ (G0 ) ,2λ′(G0 ) ,v(G0 ) }.最后证明了对任意满足 0≤s≤k- 3的整数s,存在度为k的点可迁连通图G满足λ′(G)=k s当且仅当k为奇数或者s为偶数     

高度平面图的列表L(p,q)-标号

如果平面图G的最大度Δ(G)=|V(G)|-k, k=1,2,…,则称G为一个hk-图,k=1,2的hk-图称为高度平面图.研究了高度平面图G的列表L(p,q)-标号问题, 给出了高度平面图G的列表L(p,q)-标号数λl(G;p,q)的上界,并对h1-图证明了λl(G;p,q)≤(2q-1)Δ 6(p-q);对h2-图有λl(G;p,q)≤(2q-1)Δ 8p-6q-1.     

λ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-最优图的一个充分条件.     

高度平面图的列表L（p，g）-标号

如果平面图G的最大度△（G）=｜V（G）｜-k,k=1,2,…,则称G为一个hk-图,k=1,2的hk-图称为高度平面图．研究了高度平面图G的列表L（p,q）-标号问题,给出了高度平面图G的列表L（p,q）-标号数λl（G;p,q）的上界,并对hi-图证明了λl（G;p,q）≤（2q-1）△＋6（p—q）;对h2-图有λl（G;p,q）≤（2q-1）△＋8p-6q-1．     

单圈图谱的界

设G是有n个点的连通单圈图(即恰含一个圈的连通图)。λ_1(G)是G的最大特征值。G_n是n个点的圈。S_n~3是由星图K_(1,n-1)连接它的两个度为1的点而得到的图,则下列不等式成立λ_1(C_n)=2≤λ_1(G)≤λ_1(S_n~3)左边等号成立,当且仅当G≌D_n。右边等号成立,当且仅当G≌S_n~3。     

图的λ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-正则Cayley图的l-边-连通度

介绍了l-边-连通度的定义及定义在抽象群上的Cayley图;利用构造最小l-序列边割的方法,结合Cayley图的性质,研究了3-正则Cayley图的l-边-连通度;给出并证明了l为2、3、4时的l-边-连通度λl(G);同时,给出了对n-正则Cayley图的l-边-连通度的推论.     

极小四阶限制边连通图

设G是有限简单无向图,k是正整数.使G-S每个分支的阶不小于k的边割S称为G的k阶限制边割.G的四阶限制边连通度λ4(G)是G的四阶限制边割之中最少的边数.若对于任意边e∈E(G),均有λ4(G-e)=λ4(G)-1,则称G是极小四阶限制边连通图.定义ξ4(G)=min {(e)(U):U(∪)V(G),G[U]是四阶连通导出子图},此处(e)(U)表示恰好有一个点在U上的边的数目.若λ4(G)=ξ4(G),则称G是λ4最优的.若每个5阶限制边割都孤立出G的一个5阶连通子图,则称G是超级5阶边连通的.笔者给出:极小四阶限制边连通图若不是λ4最优的,则是3正则,围长为5,任意边都关联5圈,且是超级5阶边连通的图.     

围长至少为6的平面图的L(p,q)-标号

令λp,q(G)为图G的L(p,q)-标号数,其中p和q是正整数且p≥q.证明了若G是围长g(G)≥6的平面图,则λp,q(G)≤(2q- 1)△(G) +4p +6q-5;若G是围长g(G)≥6且△(G)≠5的平面图,则λp,q(G)≤(2q-1)△(G)+ 10p-2q-4.这一结果暗含着对于g(G)≥6且△(G)≠5的平面图G,Wegner的猜想成立.     

三阶边连通度最优性的一个充分条件

设G是有限简单无向图,D,g,δ分别表示G的直径、围长和最小度.设U是连通图G的边子集.如果G-U不连通,且每个连通分支至少有3个点,则称U是G的一个三阶限制边割,|U|的最小值称为G的三阶限制边连通度,记为λ3(G).一个三阶连通子图的最小外度定义为ζ3(G)=min{|(X,(X))|:X∈V(G),|X|=3,G[X]连通}.证明如果D≤g-4且δ≥3,那么λ3(G)=ζ3(G).     

非极大弧连通有向图弧连通度的下界

设D是一个有向图,δ(D)是最小度,弧连通度为λ(D),则λ(D)≤δ(D)。当λ(D)δ(D)时,称有向图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-限制弧连通度的下界,并用例子说明所得界是紧的.     

无4,5,6-圈且无两个相交三角形的平面图的L(p,q)-标号

令λp,q(G)为图G的L(p,q)-标号数,证明了若G是不合4,5,6-圈且不含两个相交三角形的平面图,则λp,q(G)≤(2q-1)△(G)+max｛4p +4q-4,6p +2q-4,8p-4｝.这一结果暗含着对于不合4,5,6-圈且不含两个相交三角形的平面图G,Wegner的猜想成立.