路图与正则图构成的Corona图的m-度与b-染色

研究路图Pn与k-正则图G构成的Corona图PnG的m-度与b-染色.当取k-正则图G为圈图Cm、3-维超立方体Q3以及Petersen图Gp时,通过设计具体染色方案,得出图PnG的b-染色数.

(n,k)-星图网络的t/m-诊断度及诊断算法

故障诊断度在衡量多处理机系统可靠性上起着极其重要的作用.t/m-诊断分析是一种能极大提高多处理机系统自我诊断性能的诊断策略,该诊断策略能至多识别t个故障处理机,其中最多包含m个被误诊的无故障处理机.在PMC诊断模型下,证明了(n,k)-星图是n+(m-1)k-2m+1/m-可诊断的,其中2≤m≤4,且给出了复杂度为O(NlogN)的快速诊断算法来识别所有的故障节点,其中N是(n,k)-星图网络节点总数.

半群OI_n的偏度秩

设OIn是[n]上的保序严格部分一一变换半群.首次引入半群OIn的m-偏度秩的概念.对任意1≤m≤n-1,证明了半群OIn的m-偏度秩存在的充要条件是m与n互素,并得到了半群OIn的m-偏度秩均为n.

一些与圈图构成的Corona图的b-染色

图G的一个(k)b-染色是一个正常k染色,且满足在每一个色类中至少存在一个顶点,使得该顶点与其他每个色类中至少一个顶点是邻接的.图G的b-染色数用b(G)来表示,b(G)为最大的正整数k,且用k种颜色能够对G进行b-染色.对于任意的k:χ(G)≤k≤b(G),若用k种颜色能对图G进行b-染色,称图G是b-连续.通过设计具体b-染色方案,研究了Corona图CnoPm、CnoK1,m以及CnoWm+1的m-度与b-染色数,且证明这些图都是b-连续的.

一些特殊Corona图的b-连续性

图G的b-染色是一个正常顶点染色,且在每两个色类之间至少存在一条边.图G的b-染色数是最大的整数k,满足用k种颜色能对G进行b-染色,记为b(G).一个图G称为b-连续的当且仅当对于每个正整数k,χ(G)≤k≤b(G),图G存在一个(k)b-染色.本文根据Corona图的结构性质,通过设计具体染色方案的方法,证明了一些特殊Corona图的b-连续性.

Corona图P_nｏF_(1,m)、C_nｏC_m与C_nｏF_(1,m)的b-染色数

在图G=(V,E)的一个正常染色{V_1,V_2,…,V_k}中,若i,j,1≤i≠j≤k,■u∈V_i,v∈V_j,使得uv∈E,称该染色为b-染色.令b(G)=max{k|V_1,V_2,…,V_k:i,j,1≤i≠j≤k,■u∈V_i,v∈V_j,uv∈E},称b(G)为图G的b-染色数.一个图G是b-连续的,如果k:χ(G)≤k≤b(G),用k种颜色可实现对G进行b-染色.通过构造特殊染色方案,研究了Corona图P_noF_(1,m)、C_noC_m与CnoF_(1,m)的b-染色数与b-连续性.

几类Corona图的b-染色数

设{V_1,V_2,···,V_k}为图G=(V,E)的一个正常顶点染色,满足对任意的i,j:1≤i≠j≤k,存在于u∈V_i,v∈V_j,使得uv∈E,称该点染色为G的一个b-染色.一个图G的b-染色数是最大的整数k,满足用k种颜色能对G进行b-染色,用b(G)来表示.如果对任意的k:χ(G)≤k≤b(G),图G都存在一个(k)b-染色{V_1,V_2,···,V_k},称G是b-连续的.根据Corona图的结构特点,设计循环染色方案,通过对Corona图中两种类型的顶点进行循环染色,得出几类Corona图的b-染色数等于其m-度,且这些Corona图满足b-连续性.

两类图的b-染色数和研究

设图G为b-染色图,其b-染色数为φ(G)。图G的b-染色数和为φ'(G)=min{Σ_(V∈V(G))c(v)|c∈C},其中c为图G的任意一个[φ(G)]b-染色方案。通过构造染色方案与染色和分解的方法,研究了扇图F1,n与冠图PnCn的b-染色数和。

两类特殊Corona图的b-染色数与b-连续性

构造了两个特殊模型:路图(圈)与完全图中去掉一个匹配所构成图的Corona图.研究了这两个特殊Corona图的m-度与b-染色数,并证明了它们是b-连续的.

几类特殊Corona图的b-染色数与b-连续性研究

在一个图G的正常k染色中,如果每一个颜色类中都至少存在一个顶点,使得其在其它的k-1个颜色类中都至少有一个邻居,则称这样的正常k染色为b-染色.一个图G的b-染色数是最大的正整数k,使得用k种颜色能够对G进行b-染色,用b(G)来表示.如果对于任意的正整数k:χ(G)≤k≤b(G),用k种颜色可以对图G进行b-染色,则称图G是b-连续的.设G1与G2为任意图,称图G=G_1·G_2为图G_1与G_2的Corona图,其中G包含G_1的一个拷贝,包含G_2的|V(G_1)|个拷贝,且G_1的第i个顶点与G_2的第i个拷贝的所有顶点都邻接.研究了路图与路图、星形图以及轮图所构成的Corona图P_n·P_m、P_n·K_(1,m)以及P_n·W_(m+1)的m-度,b-染色数与b-连续性.

图的完全b-染色数的研究

通过将图的b-染色(数)概念的条件加强,提出图的完全b-染色(数)的概念.在b-染色问题中,染色只要求在每一个颜色类中都至少存在一个b-染色顶点,而在完全b-染色问题中,染色不但要满足上述条件,而且要求每一个顶点v,其顶点度大于等于G的完全b-染色数减1,且都是b-染色顶点.研究了路、圈、方形网格和满n叉树图的完全b-染色问题.对于路、圈、方形网格及满n叉树图,给出了染色方案,并求出了完全b-染色数.

冠图PnoSm与PnoTm,2的b-染色数与b-连续性

图的b-染色是一个满足任意两个不同色类之间至少存在一条边相连的正常点染色,把所用的最多颜色数称为b-色数.根据冠图的结构特点,通过构造具体染色方案,研究了冠图P_noS_m与P_noT_（m,2）的b-染色数与b-连续性.