路与广义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图的混合边邻域粘连度

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

广义Brandt半群上的交换图

研究广义Brandt半群上的交换图△(GB_(n))的各种图论性质:直径、围长、匹配数、独立数、团数等,分别给出了广义Brandt半群上的交换图是Euler图、Hamilton图、可平面图以及完美图的条件,探讨了广义Brandt半群上的交换图的结构.

度为2的广义星图矩阵的逆特征值问题

运用两种不同的方法对度为2的广义星图矩阵(一种特殊类型的树的矩阵)的逆特征值问题进行了深入研究。首先,引入了一种标记这种树的顶点的方案,以便以多种特殊形式表示相应的矩阵。然后,针对给定的两类不同的特征数据,将此类矩阵的逆特征值问题转化为线性方程组求解问题,得到了所研究问题有唯一解的充分必要条件。最后,给出了矩阵唯一解的表达式和相应的算法。通过数值模拟实例验证了结果的准确性。

广义齿轮图的PI指数

设G是简单连通图,e=uv是G中连接点u和点v的一条边,图G的PI指数定义为PI(G)=[neu(e|G)+nev(e|G)]。一个顶点到一条边的距离就是该点与该边的两个端点之间的最小距离。广义齿轮图是通过在圆锥图的圈上的每对相邻顶点之间添加一个顶点而得到的图,其具有优美的对称性。记广义齿轮图C*的PI指数为PI(C*),本文根据广义齿轮图的性质,得到了一种计算与一条边的两个端点距离相等的边的方法,并将其边进行分类,利用此方法找到对PI(C*)没有贡献的边,从而计算出广义齿轮图的PI指数,为研究一些特殊图的PI指数问题提供了线索。

基于Petersen图的部分重复码

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

基于图向量的一般图的广义谱刻画

给定一个图G,如果对于任意的图H,H和G同谱且它们的补图也同谱蕴含它们同构,则称图G是由广义谱确定的。在文献[12]中,作者给出了一个简单的算术条件判断一个图是由广义谱确定的,即对于给定n个顶点的图G,令其邻接矩阵和道矩阵分别为A=A(G)和W(G)=[e,Ae,…,A^(n-1)e](e为全-1向量),如果2^(-[n/2])detW(G)是无平方因子的奇数,则图G是由广义谱确定的。Qiu等^([7])通过引入图向量,给出一个与图G有关的新矩阵,将广义谱确定概念推广到一般的Φ-DS,并证明了一类正则图是Φ-DS的。本文在文献[7]的基础上,给出了判断一类一般图是Φ-DS的一个简单准则,推广了文献[12]中的结论,并通过数值实验验证了该准则的有效性。

几类特殊图的广义邻接距离谱

图谱理论近年来被很多学者广泛研究,其中对广义矩阵的研究吸引了很多学者。 最近,Pasten 和Rojo 引入了一种新的广义矩阵,为邻接矩阵和距离矩阵的凸线性组合,称为广义邻接距离矩 阵。 此外,谱极值问题也是图谱理论中的一个重要课题。 一些特殊图类经常被作为极值图类来研 究,如:块无差异图,菠萝图等。本文研究了四类特殊图的广义邻接距离谱,不仅对邻接谱和距离 谱进行了推广,也对其邻接距离谱进行了推广。

一类广义Petersen图的Wiener指标

为丰富拓扑指标的理论研究和图理论中应用价值以及突出很多物质的物理化学性质的紧密联系,研究了特殊图类的Wiener指标。通过广义Petersen图的结构特征对图的边集进行分类,最终确定了广义Petersen图的Wiener指标的精确值。这不仅体现了在并行与分布式计算中具有良好性能的Petersen图的Wiener指标在理论化学、通讯网络以及计算机系统连通方面中的应用,而且有利于分析和解决相关问题。

两类广义Petersen图的点可约边(全)染色

图G的一个(非正常)边(全)染色f满足任意两个顶点的度相同时色集合相同,则称f是图G的一个点可约边(全)染色,其中任一点的色集合为该点(或该点及其)关联边所分配的颜色构成的集合,将所用的最多颜色数称为图G的点可约边(全)色数。运用组合分析法和构造染色函数法得到了广义Petersen图P(n,1)和P(n,2)的点可约边(全)色数。

广义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图G(2m+1,m)的交叉数

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

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

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

若干广义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。

泡序图的广义4-连通度

S⊆V(G)是G的一个顶点集且|S|≥k,其中2≤k≤n.连接S的树T叫作斯坦纳树.两棵斯坦纳树T 1和T 2称为内部不交的,当且仅当它们满足E(T_(1))∩E(T_(2))=Φ和V(T_(1))∩V(T_(2))=S.令κG(S)是G内部不交的斯坦纳树的最大数目,κ_(k)(G)=min{κ_(G)(S)∶S⊆V(G),|S|=k}定义为G的广义k-连通度.很显然,当|S|=2时,广义2-连通度κ_(2)(G)就是经典连通度κ(G).因此广义连通度是经典连通度的推广.主要讨论泡序图B_(n)的广义4-连通度κ_(4)(B_(n)).得到的结论是当n_(3)时,κ_(4)(B_(n))=n-2.

广义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得到证明.