一类循环图的色数

循环图具有很强的对称性,作为有价值的通讯网络拓扑已受到广泛的关注。研究了一类循环图Ｃｎ〈１,ｋ〉,完全确定了其色数。     

有向循环图的强连通分支数以及强连通度的界

本文应用代数方法，讨论了有向循环图的强连通分支数的几种表达，以及强连通的有向循环图的强连通度的界。     

L-fuzzy拓扑空间中的强连通性

在L-fuzzy拓扑空间中引入了强连通的概念,证明了强连通的一些基本性质,并研究了强连通分支和乘积拓扑空间的强连通性,得到了一些好的结果。     

正规Cayley图

综述了自１９９０年以来１／２－传递图研究的一些新成果,正规Ｃａｙｌｅｙ图的相关结论。     

图的强染色

研究了简单图G（V，E）的强色数Xs(G）的上界与极图及Xs(G)与全色数XT（G）的关系;得到了一些特殊图的强色数Xs(G).     

具有拟极小Cayley集的Cayley图的限制性边连通度

研究具有拟极小Cayley集的Cayley图的限制性边连通度，证明了除少数例外，具有拟极小Cayley集的Cayley图是最优超级边连通的。     

右群的强半格的Cayley图

研究右群的强半格的Cayley图,刻画了这类图的结构和性质,同时还给出了一类有向图与右群的强半格的Cayley图同构的充分条件.     

一类色等价图的图特征

给出了一个有割点的连通图Ｇ是色唯一的充分必要条件为Ｇ由一个色唯一,顶点可迁图连一尾构成,进而证明了若Ｍ为色唯一,不含分离边的连通图,且Ｐ（Ｇ,λ）＝（λ－１）＾ｋｐ（Ｍ）则Ｇ含一子图同构于Ｍ及Ｋ个桥。     

强乘积图的连通度

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

3-正则Cayley图的l-边-连通度

介绍了l-边-连通度的定义及定义在抽象群上的Cayley图;利用构造最小l-序列边割的方法,结合Cayley图的性质,研究了3-正则Cayley图的l-边-连通度;给出并证明了l为2、3、4时的l-边-连通度λl(G);同时,给出了对n-正则Cayley图的l-边-连通度的推论.     

由轮生成的Cayley图的广义3-连通度

令S?V(G),κ_G(S)表示图G中内部不交的S-树T_1,T_2,…,T_r的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(T_i)∩V(T_j)=S,E(T_i)∩E(T_j)=?.定义κ_k(G)=min{κ_G(S)|S?V(G),且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.令Sym(n)是在{1,2,…,n}上的对称群,T是Sym(n)的对换集合.G(T)表示点集是{1,2,…,n},边集是{ij|(ij)∈T}的图.若G(T)是一个轮图,则将Cayley图Cay(Sym(n),T)简记为WG_n.主要研究由轮生成的Cayley图WG_n的广义3-连通度,并证明κ_3(WG_n)=2n-3,其中n≥4.     

一类高度图的均匀色数

Ｗ．Ｍｅｙｅｒ猜想,设ｎ阶通图Ｇ的最大度为△（Ｇ）,且Ｇ不为完全图和奇圈,则图Ｇ的均匀着色数Ｘｅ（Ｇ）≤△（Ｇ）。本文证明了当△（Ｇ）≥ｎ－３时,此猜想成立。     

群的Cayley图

用一些例子阐述了Ｃａｙｌｅｙ图的概念，论述了Ｃａｙｌｅｙ图的自同构群及相关结论，为进一步研究了Ｃａｙｌｅｙ图的同构五正则总是作好了了准备．。     

图乘积的分数色数

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

基于核的有向强连通图计算机随机生成算法

针对图论算法研究和算法测试对随机生成有向强连通图的需求,在深入研究有向强连通图和极小有向强连通图的结构组成的基础上,提出了有向强连通图核的概念。参考有向连通图的随机生成算法,给出了一种有向强连通图的随机生成算法,并对该算法进行了测试。对具有上千个节点及上万条弧的强连通图的随机生成,采用该算法时间都在1 s以内,生成的结果能很好地应用于图论研究,以作为图论算法的随机测试用例。     

关于临界的圆色数的一个注记

圆色数是正常着色的一个推广,由Vince在1988年首次提出．现我们考虑这样一个问题：对于Vε〉0,是否存在一个具有高连通性的临界图G使得Xc（G）≤X（G）-1＋ε？对此,Steffen和Zhu已证明对Vm≥4存在满足要求的m-连通（m＋1）-临界图,只留下一种情形未解决,即G的连通度为3时的情形．在这篇文章中我们就此情形进行讨论,并给出肯定结论．     

双Cayley图的自同构群

设G是有限群，S是G的一个子集（可能含有单位元）。群G关于S的双Cayley图BCay(G,S)是以Gx｛0，1｝为点集而以｛｛（g,0），（sg,1）｝|g∈G,s∈S｝为边集的二部图。考查了双Cayley图BCay(G,S)的自同构群A，并决定了NA(Rι^r(G)）的结构。     

Cayley有向图强连通度的进一步研究

讨论了Cayley有向图有关强连通的若干性质,应用群方法给出了一般有限群的Cayley有向图的强连通度小于其最小度的充要条件,把文献[3]的结果从循环群推广到一般有限群.