由轮生成的Cayley图的广义3-连通度

令S?V(G),κ_G(S)表示图G中内部不交的S-树T_1,T_2,…,T_r的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(T_i)∩V(T_j)=S,E(T_i)∩E(T_j)=?.定义κ_k(G)=min{κ_G(S)|S?V(G),且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.令Sym(n)是在{1,2,…,n}上的对称群,T是Sym(n)的对换集合.G(T)表示点集是{1,2,…,n},边集是{ij|(ij)∈T}的图.若G(T)是一个轮图,则将Cayley图Cay(Sym(n),T)简记为WG_n.主要研究由轮生成的Cayley图WG_n的广义3-连通度,并证明κ_3(WG_n)=2n-3,其中n≥4.     

泡序图的广义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.     

完全2-分图的l-边-连通度

连通图G所谓的l-边-连通度（Z—edge—connectivity），就是使图C成为至少l个分支所必须去掉的最少边数，记作λl（G），即λ1（G）=min{｜E’｜：E’真包含E（G），ω（G—E’）≥l}．研究了完全2-分图的l-边-连通度，得到了定理：设G=G[V1，V2]是一个完全2-分图，｜V1｜=r，｜V2｜=s，r＋k=s，k≥0为整数．则图G的（k＋2）-边-连通度为（k＋1），即λk＋2（G）=r（k＋1）．     

折叠超立方体的广义3-连通度

设图G是一个连通图,S⊆V(G)。图G的一棵S-斯坦纳树是一棵包含S中所有顶点的树T=(V ',E '),使得S⊆V '。如果连接S的两棵斯坦纳树T和T ',满足E(T)∩E(T ')=且V(T)∩V(T ')=S,则称T和T '是内部不交的。定义κ(S)为图G中内部不相交S-斯坦纳树的最大数目。广义k-连通度(2≤k≤n)定义为κ_k(G)=min{κ(S)|S⊆V(G)且|S|=k},显然,κ₂(G)=κ(G)。证明了κ₃(FQ_n)=n,其中FQ_n是n-维折叠超立方体。     

交叉立方体的限制性连通度（英文）

G是一个图,h是一个正整数,一个图G的h-限制性连通度是使得G删除G中的某个点集使得G不连通且每个分支中点的度数至少是h的最小点集的基数.交叉立方体网络是超立方体的一个变形,在平行计算系统当中交叉立方体是最重要的网络之一.该文证明了n维交叉立方体2-和3-限制性连通度分别是4n-8(n≥4)和8n-24(n≥5).     

折叠交叉立方体的2-外边连通度（英文）

g-外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且g是非负整数,如果G中存在某种边子集使得G删除这种边子集后得到的图不连通并且每个分支至少有g+1个点,则所有这种边子集中基数最小的边子集的基数称为图G的g-外边连通度,记作λ_g(G).由定义可知λ₀(G)=λ(G)并且λ₁(G)是图G的超边连通度.n维折叠交叉立方体FCQ_n是由交叉立方体CQ_n增加2^n-1条边后所得.证明了λ₂(FCQ_n)=3n-1,n≥5.     

三次图的完全扩容图的连通度

目的研究三次图的完全扩容图的连通度。方法利用反证法。结果与结论3-连通三次图的完全扩容图也是3-连通三次图。     

均衡完全三部图K3（n）的线性3-荫度

考虑均衡完全三部图K3（n）的线性3-荫度.利用路分解的方法给出了K3（n）的线性3-荫度la3（Κ3（n））当n≡1,2,3（mod 4）时的比较紧的上界,利用线性k-荫度的基本理论分别得到了它们的下界,进而得到了特殊情况下均衡完全三部图K3（n）的线性3-荫度的确切值.     

具有给定得分向量的竞赛图类的对换图的连通度

本文证明:对具有给定得分向量R的竞赛图类T(R)的对换图G(R),若G(R)至少含有三个点,且G(R)不是一个长为4的圈,则G(R)为3—连通图。这个结果加强了Brualdi和李乔在文献[1]中关于竞赛图类的对换图的2—连通的结果。     

关于图运算的和连通指标（英文）

设G=(V,E)是一个简单的连通图,V(G)和E(G)分别是图G的顶点集和边集,其中|V(G)|=n,|E(G)|=m.设d_i是点v_i的度数,i=1,2,…,n.Zhou和Trinajasti c′定义了一个新的拓扑指标,命名为和连通指标,记作X(G)并定义为X(G)=∑uv∈E(G)1/(d_u+d_v)~(1/2).该文得到了包括图的交,并,科罗纳积,笛卡尔积,和对称差的图运算的和连通指标.     

3-正则Cayley图的l-边-连通度

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

特殊符号图的符号度序列（英文）

1953年,Harary引进了符号图的概念.1994年,Chartrand等开始研究符号图的度序列.本文刻画了符号圈和符号完全二部图的度序列.     

逆度和图的性质（英文）

设G=(V(G),E(G))是n个顶点m条边的简单图.无孤立点的图G的逆度定义为■,其中,d(v_i)表示顶点v_i的度.首先用逆度刻画了连通图分别是k-哈密尔顿、k-边哈密尔顿、k-路覆盖、哈密尔顿连通、k-连通、2-边连通和β-亏损的充分条件.其次用逆度给出了连通图的独立数小于等于整数k的充分条件.最后用逆度给出了连通的平衡二部图是哈密尔顿图的一个充分条件.     

广义超立方体的广义连通度

k元n方体是著名的超立方体网络的推广。针对k元n方体的广义3-连通度问题,证明了对任意的整数k≥3和n≥1,k元n方体中存在2n-1棵内部不交的连接任意3个顶点的树。     

广义Petersen图的控制数(n=3k)（英文）

如果VS中的每一个点都与S中的至少一个点相邻,我们称V的子集S是G=(V,E)的一个控制集.G的控制数是G的最小控制集的基数.许多类型图的控制数及其算法已经被研究,通常这些图都有某种树型结构.本文将确定广义Petersen图当n=3k时的控制数,且其控制数为[5n/9].     

图的代数连通度及其点连通度

G是一个简单图.a(G),k(G)分别为G的代数连通度和点连通度,该文刻画了满足a(G)=k(G)的图.G=(V,E)是一个n阶简单图,点连通度为k(G)≤[n/2].H是G的任意最小点割集,则a(G)=k(G)当且仅当对任意u∈H和v∈V\H,有uv∈E.     

连通[5，3]-图的最长路（圈）

如果G中任意s个点的导出子图中至少含有t条边,则称G为[s,t]图.文中证明了:阶数不小于6的连通[5,3]图的最长路的长度不小于n-2,且路长的界是紧的,其最长圈的长度可任意小.     

变换图G++-的连通度

本文所研究的图G的变换图G++-是以V(G)∪E(G)作为顶点集的图,它的两个顶点u与v被一条边连接当且仅当下列情形之一成立:(ⅰ)如果u,v∈V(G),那么它们在G中邻接.(ⅱ)如果u,v∈E(G),那么它们在G中邻接.(ⅲ)如果u与v一个属于V(G)而另一个属于E(G),那么它们在G中不关联.文章给出了变换图G++-的连通度的一个下限.     

具有乘积度-基尔霍夫指标极值的双圈图（英文）

对于一个图G,乘积度-基尔霍夫指标定义为R*(G)=∑{x,y}■V(G)dG(x)dG(y)rG(x,y).基于前人的一些研究成果,用类似于和的度-基尔霍夫指标应用在双圈图中的方法,把乘积度-基尔霍夫指标运用到双圈图中.首先给出了关于R*(G)的一些图变换,然后根据这些图变换,确定了恰好有两个圈的n阶双圈图的最小和最大的乘积度-基尔霍夫指标的值及其对应的极值图.度-基尔霍夫指标广泛应用于电流网络、化学、马尔可夫链和欧氏距离等各个方面.     

完全图半群与连通图半群

引进了拟完全国半群、完全图半群、连通图半群以及连通元的概念，证明了有限字母在上的自由半群和相应的完全图半群同构；是可换图。另外，给出了ｎ阶连通简单图半群有Ｓ阶完全子图半群的一个充分条件。