完美C-超图的一个充分条件

混合超图是含有两种超边的超图，一种称为D-超边，一种称为C-超边，它们的区别主要体现在着色要求上．在任一着色中，要求每一D-超边至少有两个点着不同的颜色，每一C-超边至少有两个点着相同的颜色．只含D-超边的超图称为D-超图，只含C-超边的超图称为C-超图．主要讨论了C-超图的完美性问题，给出了完美C-超图的一个充分条件．     

4一致C-超图的最小边数问题

研究了上色数为3的4一致C-超图的最小边数问题，并给出了上色数为3的4一致C-超图的最小边数的一个上界．     

超图的最短路径算法

从超图的强同构引出保持超图顶点间超邻接性的点同构,定义超图的邻接矩阵和赋权超图的权矩阵,并在此基础上得到了求解超图任意顶点间最短路径和求解超图直径的推广Floyd算法.最后通过实例验证了算法的可行性,并与李春明在1994年得到的结果进行比较,得出算法的复杂度为O(n3),该算法是一个有效算法.     

混合图的边着色

著名学者Daniel Krlá.,Jan Kratochvlí,Heinz-Jürgen Voss等曾在其著名论文《Mixed hypergraphs with bound-ed degree：edge-coloring of mixed multigraphs》中提出任何一个混合超图均可一一对应地转化成一个最大度不超过3的混合超图,且它们的着色亦是一一对应的。因此,研究最大度为3的混合超图的着色问题具有一般性,是困难的;而研究最大度为1的混合超图的着色问题是平凡的;所以我们着力研究最大度为2的混合超图。而最大度为2的混合超图的点着色问题可以一一对应地转化为一个与其对应的混合多重图的边着色问题,因此,文章从特殊的混合多重图-混合图入手,着力研究混合图的边着色。     

7人参与的一类超图存取结构的最优信息率

运用存取结构与连通超图之间的关系,将7人参与的一类存取结构转化为连通超图中顶点数为7的一类共94种超图存取结构,研究了最优信息率及其所对应的完善秘密共享方案的构造.运用超图理论及方法对其中80种超图存取结构最优信息率的精确值进行了计算,并给出达到此信息率的秘密共享方案的具体构造方法;对其余的14种超图存取结构运用λ-分解等方法给出最优信息率的上下界.证明了具有n个顶点且秩为r的超图,其超边数至少为(n-r)/(r-1)+1条,至多为Cr n条;并从理论上证明了满足一定条件的顶点数为n(4≤n≤9),超边数为4且秩为3的非理想超图的最优信息率为2/3.     

混合多重图的边着色

著名学者Daniel Král. ,Jan Kratochvil, Heinz-Jürgen Voss等曾在其著名论文《Mixed hypergraphs with bounded degree：edge-coloring of mixed multigraphs》中提出任何一个混合超图均可一一对应地转化成一个最大度不超过3的混合超图,且它们的着色亦是一一对应的。因此,研究最大度为3的混合超图的着色问题具有一般性,是困难的;而研究最大度为1的混合超图的着色问题是平凡的,所以我们着力研究最大度为2的混合超图。而最大度为2的混合超图的点着色问题可以一一对应地转化为一个与其对应的混合多重图的边着色问题,因此,本文作者着力研究混合多重图的边着色。     

参与者人数为9的一类连通超图存取结构的信息率

基于存取结构与连通超图之间的关系,给出了顶点数为9,秩为3,超边数为4和5的一共226种不同构的连通超图存取结构,进而估算了它们的最优信息率。本文首先证明了具有4条超边的一类超星可以用理想的秘密共享方案来实现,并证明了满足一定条件的顶点数为n(5≤n≤11),超边数为5且秩为3的连通超图其最优信息率的下界为2/3。运用超图的相关理论对其中的16种超图存取结构最优信息率的精确值进行了计算,对余下的210种超图存取结构进行了分类,并估算了这些超图存取结构最优信息率的界。     

铺砌(3.6.3.6)的圆内C-点数

设C-点为阿基米德铺砌(3.6.3.6)的顶点.确定了以任意C-点为圆心.以r= √n(n∈Z+)为半径的圆D(n)的内部及边界上所含的C-点数.N(n),并进一步证明了limn→∞N(n)/n=√3/2π.     

给定悬挂点数和谱半径最大的连通k一致超图的结构

设?是n阶且悬挂点数为r的连通k一致超图的集合,其中n-r=k-4.利用特征方程的方法,刻画了图类?中谱半径最大的k一致超图的结构.     

线性超图的边着色问题

设S是由边秩大于等于3的边导出的部分超图,q表示超图的边色数。本文给出了满足Δs=2,qs=3,这类线性无环超图边色数的上界。进一步得到了n个顶点的无环线性超图H,如果满足Δs≤3,qs≤3,则q(H)≤n。此外,还讨论了r阶射影平面的边色数q(H)=r2-r+1。     

轮形图的全着色

图G(超图H)的全着色是指同时给图中的顶点和边进行着色,使相关联或相邻的元素间着不同的颜色,而使用的最少的颜色数就称为全色数,记为xT(G)(xT(H)).超图的全着色又可以分成弱全着色和强全着色2种情况.本文主要讨论超图中轮形图W(v)的全着色性质,并得到具体的强全色数和弱全色数,xWT(W(v))=△+1,xST(...     

D-完全一致混合超图上色数的研究

混合超图的上、下色数与C-超边和D-超边数有着必然联系.一般地,增加C-超边会使下色数χ（H）增加,增加D-超边会使上色数χ-（H）减小.本论文对D-完全一致混合超图的上色数进行了研究,并得到一些初步的结果.     

若干倍图的Smarandachely邻点边染色

图G(V,E)的Smarandachely邻点边色数是满足条件uv∈E(G),|C(u)＼C(v)|≥1并且|C(v)＼C(u)|≥1的一个正常边染色的最小边色数,其中C(u)=｛f(uv)|uv∈E(G)｝。给出了路、圈、星、扇图的倍图的Smarandachely邻点边色数。     

图的星边星-全色数的一个上界

提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,边进行星边染色.并定义图的星边星-全色数,记为χsTs(G).用构造染色的方法给出一些特殊图(路,圈,轮,扇,完全图)的星边星-全色数.同时运用概率方法给出满足一定条件的图G的星边星-全色数的一个上界,即若图G的最大度Δ(G)≥30,则χsTs(G)≤24(Δ-1)3/2.     

轮和路的广义Mycielski图的星全染色

图G的一个正常全染色被称作G的星全染色,如果G中任意路长为2的点和边着色均不相同.图的全部星k-全着色中最小的数k称为它的星全色数.讨论轮和路的广义Mycielski图的星全染色问题,得到不同情况下它们的星全色数,其中每个点的色集合包含该点及其关联边的颜色.     

图的强直积的2-距离染色(英文)

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。     

若干联图的星全染色

图G的一个正常全染色如果满足G中任意路长为2的点和边着色均不相同,称为G的星全染色.图的全部k-星全染色中所用最少的颜色数称为图G的星全色数.文章研究了若干联图的星全色数.     

几个特殊图的全着色

设G是一个图,G的全着色是一个映射π:V(G)YE(G)C,使得相关联或相邻的元素着不同色;G的所有全着色中,使得色数的最小者,称为G的全色数,记为χT(G);得到了几个特殊图的全色数     

广义r-部完全超图的边色数

研究了广义r-部完全超图的边色数的问题.在r-部完全超图与t-一致完全超图的着色基础上,确定一类特殊的广义r-部完全超图的边色数,对一般的广义r-部完全超图的边色数给出了上界,推广了r-部完全超图与t-一致完全超图的着色结论.