路与广义Petersen图的直积图的Wiener指数

图G和H的直积图G×H是一个顶点集为V(G)×V(H)的图,两点(g_(1),h_(1))和(g_(2),h_(2))是相邻的当且仅当g_(1)g_(2)是图G中的一条边,h_(1)h_(2)是图H中的一条边.连通图G的Wiener指数,记作W(G),是图G中无序点对之间的距离之和.最后得到了路与广义Petersen图P(m,3)的直积图的Wiener指数.

广义Petersen图的2-HC-可扩性

结合连通图的可扩性和哈密尔顿性,2012年MIKLAVIC等提出了连通图的可扩性。如果连通图Γ包含l-路且每条l-路均可扩充为Γ的一条哈密尔顿圈,那么称Γ是l-HC-可扩的。利用连通图的圈的对称差构造哈密尔顿圈,并证明了广义Petersen图GP(n,k)是2-HC-可扩的,其中k=1,2和3。

基于Petersen图的部分重复码

为对分布式存储系统的修复效率研究,提出一种基于Petersen图边染色的部分重复码设计。该设计利用Petersen图边染色进行构造,即先对Petersen图的边进行染色,标记出染色的不同边数,然后构造Petersen图中不同边色的链路,最后把每条链路视为部分重复码的存储节点,称为PECBFR码。理论分析指出,PECBFR码可以随机访问模式下的系统存储容量。此外,实验仿真结果显示,本文提出的基于Petersen图边染色的部分重复码构造算法,与分布式存储系统中的里所码以及简单再生码相比,在系统修复故障节点时,能够快速地修复故障节点,通过染色链路构造的部分重复码,在修复局部性、修复复杂度、修复带宽开销相较于分布式存储系统中的常见编码算法都有较大的性能提升。

广义Petersen图的混合边邻域粘连度

已知图的混合边邻域粘连度概念以及几类基本图的参数计算公式后,本文给出了广义Petersen图的混合边邻域粘连度的计算公式,使得混合边邻域粘连度算法更为细化,刻画某些网络的抗毁性更为精确。

广义Petersen图的L(d,1)-标号

图G的顶点集到非负整数集的一个映射f满足:对任意的x,y∈V(G),当dG(x,y)=1时,有f(x)-f(y)≥d;当dG(x,y)=2时,有f(x)-f(y)≥1。图的一个k-L(d,1)-标号是指图的一个标号L(d,1)使得min{f(v)|v∈V(G)}=k,标号数简记为λd(G)。研究了广义的Petersen图的标号L(d,1),给出一个特殊的标号方法,得到了广义的Petersen图的标号数λd(G)≤4d。

双环Petersen图互联网络及路由算法

Petersen图由于具有短直径和正则性等特性,因此在并行与分布式计算中具有良好的性能.基于双环结构,构造了一个双环Petersen图互联网络DLCPG(k).同时,分别设计了DLCPG(k)上的单播、广播和容错路由算法.证明了DLCPG(k)不但具有良好的可扩展性、短的网络直径和简单的拓扑结构等特性,而且对于10k个节点组成的互联网络,DLCPG(k)还具有比二维Torus以及RP(k)互联网络更小的直径和更优越的可分组性.另外,还证明了其上的单播、广播路由算法的通信效率与RP(k)上的单播和广播路由算法的通信效率相比均有明显的提高.仿真实验表明,新的容错路由算法也具有良好的容错性能.

广义Petersen图G(2m+1,m)的交叉数

先利用去边的方式证明了广义Petersen图G(2m+1,m)的交叉数的下界是3,然后证明它的交叉数就是3.

基于超立方体环连接的Petersen图互联网络研究

基于环的简单扩展性,Petersen图的短直径与超立方体互联网络中节点的高可连接性相结合,提出了一种新型互联网络RHP(n)(Ringed Hypercube Connected Petersen),并对其特性进行了研究.证明了 RHP(n)网络不但具有正则性以及良好的可扩展性,同时还具有比 Qn、HP(n)网络更短的直径和更小的构造开销.另外,还基于RHP(n)网络分别给出了其上的单播和广播路由算法,证明了其通信效率分别为n-1和n-1.

广义Petersen图G(n,k)的邻强边染色

研究了若干广义Petersen图G(n,k)的邻强边染色,证明了若n≡0(mod 4),k≠0(mod 4), 则X'as(G(n,k))=4.

基于Petersen图互连的超立方体网络及其路由算法

提出了一种新型互联网络PGCH(Petersen Graph Connected Hypercube),并对其特性进行了研究。证明了PGCH(k)网络不但具有正则性以及良好的可扩展性,同时还具有比Qk、TQk、CQk、以及HP(k)网络更短的直径和更好的可连接性。另外,还基于PGCH(k)网络分别给出了其上的单播、广播和容错路由算法,证明了其上的单播、广播路由算法的通信效率分别为k-2和k-2.且仿真实验表明,PGCH(k)上的容错路由算法具有良好的容错性能。

Torus连接Petersen图互连网络及路由算法

可扩展性和短直径是设计大规模并行计算机系统互连网络的两个重要因素。基于Petersen图的短直径和正规性和Torus拓扑结构的可扩展性,提出了一种新的互连网络拓扑结构,称为Torus连接Petersen图互连网络。该互连网络拓扑结构具有短直径、正规性、对称性和良好的扩展性。网络节点采用混合编码方法,使得路由算法设计简单。分别设计了基于混合编码的单播、广播路由算法。分析表明提出的互连网络具有较好的拓扑性质。

剖分Petersen图得到的新测地块(英文)

通过剖分Petersen图我们得到了一类新的测地块.由此成功构造了给定直 径为6和围长为11的测地块,解决了近二十年来悬而未决的一个存在性和构造性问题.

若干广义Petersen图的邻点可区别全染色

研究了若干广义Petersen图G(n,r)的邻点可区别全染色。构造性地证明了:若n≡0(mod 4),r■0(mod 4)或n≡0(mod 5),r■0(mod 5),则G(n,r)的邻点可区别全色数为5。

Petersen图的Hamilton性和边色数(英文)

对简单图G(V ,E) ,定义图G的关联图I(G)为V(I(G) ) ={ (ve)｜v∈V(G) 且e∈E(G) 和v与e关联 } ,E(I(G) ) ={ (ue ,vf)｜u=v或e=f或uv =e或uv=f} .本文证明了Petersen图可被分解为边不交的Hamilton 圈和一个 1

广义Petersen图的控制数——当m为奇数时P(m,2)的控制数

广义Petersen图是一类重要的并被广泛研究的互联网络. 得到了广义Petersen图P(m,2)当m为奇数时的控制数的一个可达上界.

广义Petersen图的最小点覆盖集

点覆盖问题是一个著名的NP完全问题.本文对广义Petersen图P(n,2)的精确最小点覆盖数进行研究,讨论并证明了广义Petersen图P(n,2)的最小点覆盖数,给出了最小点覆盖集的构造方法.

两类广义Petersen图的Euler亏格

广义Petersen图P(n,m)是这样的一个图:它的顶点集是{u_i,v_i|i=0,1,…,n-1},边集是{u_iu_(i+1),v_iv_(i+m),u_iu_i|i=0,1,…,n-1},这里m,n是正整数、加法是在模n下且m<[n/2].这篇文章证明了P(2m+1,m)(m≥2)的Euler亏格是1,并且P(2m+2,m)(m≥5)的Euler亏格是2.

一类广义Petersen图的邻强边染色

研究了一类广义Petersen图G（n,k）的邻强边染色,构造性地证明了：若n≡0（mod3）,k≡/0（mod3）,则χ（as）′（G（n,k））=4.其中χas′（G（n,k））表示G（n,k）的邻强边色数.

广义Petersen图在四种可区分条件下的全染色（英文）

关于图的可区别染色的研究起源于移动通信的频率分配问题.本文定义了简单图G的一个4-邻点可区别全染色.对一个图G进行4-邻点可区别全染色所需的最少颜色数称为图G的4-邻点可区别全色数,记为x〃_(4as)(G).对于广义Petersen图P(n,k),6≤x〃_(4as)(P(n,k))≤7得到证明.

Petersen图的反Ramsey数

给出Petersen图的反Ramsey数AR(n,P)的上下界.若n≤9,则AR(n,P)=n(n-1)/2.若n≥10,则当n为奇数时,t(n,2)+2≤AR(n,P)≤t(n,8)+1;当n为偶数时,t(n,2)+3≤AR(n,P)≤t(n,8)+1.