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

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

k元n方体网络的4-限制边连通度

l-限制边连通度是边连通度的推广,可更精确地度量网络的可靠性.k元n方体网络因其特殊的结构和良好的性质成为多处理机系统最常用的互连网络之一.证明了k元n方体的4-限制边连通度和它的最小4-度相等,并确定了它们的值.所得结果说明,当用4-限制边连通度作为度量指标时k元n方体是可靠的.     

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

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.     

极大局部边连通和超级局部边连通有向图的度条件

证明了超级局部边连通有向图的最小度条件:如果n≤2δ,则排除一类图后,图为超级局部边连通的。此外还给出了极大局部边连通和超级局部边连通有向图的一些度序列条件。     

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

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

k度Steiner最小权网络的线性时间算法

已知平面上n个固定点集合N和m个可动点集合M,求互连点集N∪M的最短连通网络,要求这个连通网络满足：（1）固定点的度为1,可动点的度为k(k≥3）;（2）n=2 （k-2）m。网络中每条边的权与可动点的位置有关,问题是如何确定这m个可动点的位置,使这个连通网络的权最小,这个问题称为k度Steiner最小权网络问题。本给出了k为偶数,边权值为L1距离时计算最小权网络的O(n ln k)时间算法。     

笛卡尔乘积图的限制边连通性

设G是一个极大限制边连通k-正则图,k≥2．论文证明了：如果│G│〉2k且n≥3,那么笛卡尔乘积图Pn×G是超级限制边连通的,除非G包含子图Kk;如果│G│〉k＋1且n≥3,那么Cn×G是超级限制边连通的,除非n=3且G是圈．     

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

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

讨论连通的残差完备图,确定了连通的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阶的残差完备图.     

图有较高连通度的一个充要条件

图的连通性理论是图论学科重要而基础的研究领域,通过该领域的研究,人们对图的结构和性质有了进一步的认识,并且将所得到的结果应用于网络设计、城市交通等实际问题中,取得了很多应用成果,例如,量化一个图或网络的脆弱程度,便始于图的连通性研究。因此,我们总是希望图能具有较高的连通度。对n个顶点的图G来说,当连通度不小于顶点数n的一半时,我们认为这个图有较高的连通度。本文试图给出图具有较高连通度的一个充分必要条件。我们指出,对一个给定的正整数k且k≤2n,有κ(G)≥n-k成立当且仅当对顶点集V(G)的任意一对不交子集S和T,G[S,T]有一个完美匹配,这里|S|=|T|=k,G[S,T]=G[S∪T]-E(G[S])-E(G[T])。     

超立方体网络的限制边连通性

m-限制边割将连通图分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图的m-限制边连通度.本文给出了n立方体的m-限制边连通度的表达式,由此推出：当m≤2（n/2）-1或m=2 k≤2n-1（k为任意正整数）时,超立方体Qn是极大m-限制边连通的.     

完全对换图的广义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个连接它们的内部不交的树.     

由2-树生成的Cayley图的容错极大局部连通性

主要证明了由2-树生成的Cayley图A_n(Δ)(n≥5)是(2n-7)容错极大局部连通和一对多(2n-7)容错极大局部连通。限制每个顶点有至少3个无故障邻点,则A_n(Δ)(n≥5)是(4n-15)容错极大局部连通。     

具有2K个奇度点的p阶标号图的计数

本文研究具有2k个奇度点的P阶标号简单图的计数问题.考察了下列情况:i/具有2k个奇度点的P阶标号简单图;ii/具有2k个奇度点的P阶标号连通简单图;iii/具有2k个奇度点的标号(P,q)图;iv/具有2k个奇度点的标号(P,q)连通图.对每一种情况,给出了它们的递归计数式和通过电子计算机获得的若干结果.     

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

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

图的最大匹配个数的下界

设G是一个具有n个顶点且最大匹配为k-匹配的连通图,这里n≥2k+1.证明了G至少有n-2k+1个互不相同的最大匹配,并且刻画了恰好具有n-2k+1个最大匹配的图.     

k元n方体的边容错性

k元n方体是并行与分布式处理系统最常用的互连网络拓扑结构之一.研究了k元n方体中不存在k元(n-m)方体子结构的最小边故障数目fn,m,其中k≥3是奇数,证明了fn,0=1,kn≤fn,m≤n(mm)k,fn,n-1=nkn-1以及fn,1=k+k/(n-1).     

Wiener指数,Hyper-Wiener指数与泛圈图

设G=(V,E)为n阶简单连通图,若对每一个k(3≤k≤n),都含有长度为k的圈Ck,则称G为泛圈图。本文主要利用图及其补图的Wiener指数、hyper-Wiener指数,给出具有最小度条件的简单连通图是泛圈图的充分条件。     

(n,k)-星图的嵌入连通度

星图S_(n,k)的h-嵌入连通度ζ_h(S_(n,k))(h-嵌入边连通度η_h(S_(n,k)))被定义为顶点子集(边子集)的最小基数,如果存在,将其删除后Sn,k不连通而且连通分支的每个顶点都位于h-维的子网络Sh,l,其中0≤h≤n-2且l≤k.本文研究了星图S_(n,k)的h-嵌入(边)连通度,对于k=2,3和0≤h≤n-2,确定了ζ_h(S_(n,k))和ηh(S_(n,k))的值.     

含有故障点的4元n方体中无故障路的嵌入

k元n方体是传输信息的一种重要网络.本文研究含有故障点的4元n方体,证明了当其故障点数f（≤n-1）时,对每个奇数l∈{2n-1,2n-3,…,4n-2f-1},任意两个相邻的非故障两点之间存在长度为l的无故障路.