基于强乘积运算下图的广义和连通度指标上下界

对于图G,令E(G)表示G的边集,令V(G)表示G的点集,d_(G)(v)表示v的度。对于边e=uv,定义广义和连通度指标χ_(α)(e)=(d_(G)(u)+d_(G)(v))^(α),其中α为任一实数。本文先介绍了图的S,R,Q,T四种运算,然后给出了四种运算下的强乘积,并利用最大度最小度确定了其四种图的广义和连通度指标的上下界。

路与星图的强乘积图的容错直径

设路P_(m)与星图S_(1,n-1)的强乘积图为G=P_(m)S_(1,n-1).首先,通过归纳假设和构造内点或边不交路的方法,结合星图的中心性,给出图G的点容错直径D_(w)(G)和边容错直径D′t(G).结果表明,对图G中发生的任意点或边故障,都有D_(w)(G)≤d(G)+2,D′t(G)≤d(G)+1.其次,通过顶点数和边数构造的不等关系,给出两个极大连通图的强乘积图的点容错直径的上界,以及两个非平凡连通图的强乘积图的边容错直径的上界.

完全图强乘积的强半径和强直径

首先证明2个非平凡完全图强乘积是完全图且具有强定向性,然后确定了完全图强乘积的最小强半径和最小强直径的精确值,给出了最大强直径和最大强半径的范围.最后通过利用强乘积的结合性,将上述结论推广到多个完全图的强乘积.

三个图强乘积点转发指数的下界

网络通信系统性能的有效性取决于网络中路由选择的优劣.点转发指数就是度量路由选择优劣的一个重要参数.利用强乘积方法,可以将小型网络构造成大型网络.通过分别研究所用小型网络和所得大型网络的拓扑结构参数,确定了三个任意连通图强乘积点转发指数的下界,并且得到了一些特殊强乘积图点转发指数的具体下界.

强乘积图的连通度(英文)

用iκ>0和iδ表示图Gi(i=1,2)的连通度和最小度,给出了无向图强乘积的连通度一个下界:κ(G1G2)≥min{1κ(1+2δ),2κ(1+1δ)}.

图的强乘积的带宽

本文讨论了由两个图的强乘积所导出的一些特殊图的带宽.

强乘积图的连通度和边连通度(英文)

研究了两个图G1和G2的强乘积图G1■G2的连通度和边连通度.这里证明了λ(G1■G2)=min{λ1(n2+2m2),λ2(n1+2m1),δ1+δ2+δ1δ2},如果G1和G2都是连通的;还证明了κ(G1■G2)=min{δ1n2,δ2n1,δ1+δ2+δ1δ2},如果G1和G2都是极大连通的.其中,ni,mi,λi和δi分别表示Gi(i=1,2)的阶数、边数、边连通度和最小度.

强乘积图的Euler性

强乘积是一种通过若干规模较小的网络构造出规模较大的网络的方法,由此构造出来的大网络包含小网络作为它的子网络,并且保留了小网络一些好的性质,如连通性、可嵌入性等.强乘积图 G1 - G2 的拓扑结构由乘积因子图 G1 和 G2 的拓扑结构所决定.图的 Euler 迹问题是图论中一个重要的问题,在实践中也有着许多应用.本文通过因子图来研究强乘积图的 Euler 环游和 Euler 通路问题,得出并证明了两个图的强乘积存在 Euler 环游和 Euler 通路的充分必要条件.

强乘积图与字典乘积图的控制数

证明了:1)图G和H的强乘积图GH的控制数γ(GH)≤γ(G)γ(H),并举例说明此上界是可以达到的;2)若γ(H)=1,则G与H的字典乘积图的控制数γ(G H)=γ(G);若G不含孤立点并且γ(H)≥2,则γ(G H)=γt(G),其中γt表示图的全控制数.

路与路强乘积的最小直径定向

给定一个无向图G,将G的每条边{xy}用弧xy或yx替代得到的有向图称为G的的定向图。使得G的所有定向图中直径最小的定向图称为G的最小直径定向。文章给出了两条路强乘积的最小直径定向。

强乘积图的宽直径上界

由于图本身可以表示网络的拓扑结构,所以研究网络的各类指标时,常常使用图的参数和性质来度量网络性能的优异.通常是使用乘积图用小因子图构造复杂大图,其中使用强乘积来构造图是一种重要的构造图的方法,而宽直径则是度量网络性能的重要参数.宽直径较小的网络往往拥有较小的传输延迟.本文给出了任意两个因子图进行强乘积之后的乘积图,并根据子图的两种属性得出了宽直径上界,最后举例说明了使用强乘积图构造网络和使用笛卡尔乘积图构造网络的优点与不足.

强乘积图的限制边连通度

文章研究了两连通图G1和G2的强乘积图G1G2的限制边连通度,给出了强乘积图的限制边连通度的一个上界,并确定一类特殊强乘积图的限制边连通度.

两条奇长路的强乘积精确Wiener指数

一个简单有限连通图G的所有无序顶点对之间的距离之和称为G的Wiener指数,用W(G)来表示.主要研究了一类给定阶数的路的强乘积Wiener指数,利用强乘积图的结构特征,刻画了当路径长度为奇数时,两条路强乘积的精确Wiener指数.除此之外,还给出了两条路强乘积边转发指数的一个上界.

一些乘积图的覆盖数(英文)

在图上进行小石块的移动的步骤为从一个点上取走两个小石块,并在它的某个邻点上放一个小石块.显然存在某个自然数,当图的所有点上的小石块的总数大于或等于它时,无论小石块在图上是如何初始分布的,都可以经过一系列的上述步骤,使得每个点上都至少有一个小石块.对一个图而言,满足此条件的最小的自然数即为此图的覆盖数.解决了字典乘积图和一些强乘积图的覆盖数问题,并给出了任意一个图的关键点与直径的两个端点之间的关系.

图乘积的分数色数

在文中我们对两个图的强乘积的分数色数进行了研究.任意给定两个图G和H,我们证明了ω(G)ω(H)≤χf(GH)≤χ(G)χ(H),这里ω(G)表示图G的最大团所含顶点的个数,χf(G)和χ(G)分别表示图G的分数色数和色数.从而我们可以通过图G和H本身的性质来对它们的强乘积的分数色数和色数进行估计.

某些有向图的几类乘积图的多数染色

将某些有向图的几类乘积图作为研究对象,对多数染色开展研究,并证明多数染色猜想对该类图是成立的。

一些特殊图类的常见三种乘积的边完整度

本文确定特殊图类完全图和路图的常见三种乘积笛卡儿乘积,直接乘积,强乘积的边完整度。

几类图的Wiener数及平均距离

设G=G1G2是G1和G2的强乘积,算出了图PnPn,θ(l,n)及DB(d,2)的Wicner数及平均距离。

关于C_rC_n的Hamilton分解

给出了C3 Cn 和C4 C2n+ 1的Hamilton分解 ,证明了

两类特殊图的最优填充

运用图的最优填充分解定理,将强乘积图P3 Pn,P2 Pn与乘积图P2×P2n进行分解,得到了它们的最优填充数.