完全k部图的指标

讨论了完全多部图指标所对应的特征向量的性质，指出了有ｎ个顶点的所有ｋ部图指标间的关系及具有最大，最小指标的图。同时确定了有ｎ个顶点的ｋ色图的集合中具有最大指标的图。

完全k部图和一些特殊图的CORDIAL性

给出了完全k部图是Cordial图的充要条件，并给出此类Cordial图的Cordial标号;给出n阶Cordial图的最大边数,关构造了相应的极图;给出正则图是Cordial图的必要条件;解决了轮的Cordial问题.

完全K部图的Hosoya指标和Merrifield-Simmons指标极图

图的 Hosoya指标和Merrifield-Simmons 指标是化学图论中两个重要的拓扑指标.考虑点数为n的完全 K 部图集合K n1,n2,…,nk ,证明了在图集Kn1,n2,…,nk 中K1,1,…,1 k-1个,n-k+1 具有最小的 Hosoya指标和最大的Merrifield-Simmons 指标,并且图Kq,q,…,q k-r个, q+1,…,q+1 r个在K n1,n2,…,nk 中具有最小的 Merrifield-Simmons指标和最大的Hosoya指标,其中 n= kq+r,0≤r<k.

三部图的K_3-匹配问题

文章就三部图的匹配问题进行了研究,描述了K3 匹配的定义,提出2-匹配的概念,给出三部图存在K3 匹配的充要条件及有关三部图的2-匹配的性质,为解决复杂的指派问题奠定了一定的理论基础。

偶图K_(n,n)-I的循环m-圈分解

设Kn,n表示每部分具有n个顶点的完全二部图,I为Kn,n的一因子.讨论了Kn,n-I的循环m-圈分解的存在性,并给出了Km+1,m+1-I存在循环m-圈分解的一个充分必要条件.

完全二部图的t-pebbling数

图G的t-pebbling数ft(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列pebbling移动把t个pebble移到任意一个顶点上,其中的pebbling移动是从一个顶点上移走两个pebble,而把其中的一个移到与其相邻的一个顶点上,本文确定了完全二部图t-pebbling数,作为推论给出了完全K部图的t-pebbling数。

正则二部竞赛图中点不相交的回路与拟回路

本文证明了,对任意大于1的整数k_1+k_2=2k,k 正则二部竞赛图R 中含有两个点不相交的回路C_(2k1) 和C_(2k2) 或拟回路C2_(k2) ,除非R≌R.

正则二部竞赛图的竞争指数

设D是一个有向图,如果存在无向图G满足V(G)=V(D),且对G中任意的顶点x,y相邻当且仅当G中包含顶点z,使得存在从x到z以及从y到z的长为m的途径,则称G为D的m步竞争图,记为C^(m)(D).若存在最小正整数q,使得C^(q+i)(D)=C^(q+i+r)(D),其中r是某个正整数,i是所有非负整数,则称q为D的竞争指数,记为cindex(D).给出了几乎正则二部竞赛图的竞争指数等于1时的充要条件,并进一步刻画了k正则二部竞赛图的竞争指数等于1和2时的充要条件。

图的强符号圈控制数

本文研究了图的强符号圈控制数γ′_(ssc)(G).利用最大独立集最大匹配等方法,刻画了满足γ′_(ssc)(G)=|E|-2的所有连通图,给出了γ′_(ssc)(G)的一个下界,求出了两类特殊图的强符号圈控制数.

关于乘积图的二维带宽问题

给出一般乘积图的二维带宽的界，并解决一类乘积图的二维带宽问题．最后给出完全ｋ部图的二维带宽。

极图理论初探

本文讨论了图论中的极图理论问题，给出了极图理论的几点结论。

关于K_（1，2，n）和K_（1，1，1，n）的优美性

分别给出了完全３部图Ｋ１，２，ｎ和完全４部图Ｋ１，１，１，ｎ的一种优美标号，从而证明了Ｋ１，２，ｎ和Ｋ１，１，１，ｎ是优美图．

互连网络的新模型:多部群论模型

互连网络是超级计算机的重要组成部分。互连网络在很大程度上决定着超级计算机的性能。在1989年,S.B.Akers等提出了互连网络的群论模型,据此模型设计出了星网络、冒泡排序网络等一大批网络。尤其是星网络具有很多很好的性能,被认为是超立方体的替代品。但它们都有一个弱点:网络规模(结点数)为n!。即随着n的增大,n!增速太快,使得据此网络结构设计出的超级计算机升级较为困难,即扩展性较差。在群论模型的基础上提出了互连网络的多部群论模型,进而,据此模型设计出(n,k)-多部星网络、(n,k)-多部冒泡排序网络等多种网络。并证明星网络是(n,1)-多部星网络,而且(n,k)-多部星网络做到了规模(结点数)增大且增幅固定、直径增大缓慢、结点度不变,即有很好的可扩展性,其它(n,k)-多部网络也有类似的性能。

有关树的联图的厚度

图G的厚度θ(G)是指图G分解为平面生成子图的最小数,它是度量图的平面性的重要指标.图的厚度不仅仅在理论上有着重要的研究价值,它在超大规模集成电路和网络设计中也有着重要的应用.研究了与树有关的3类联图的厚度,第1类是完全图与树,任意包含n个顶点的图与树的联图;第2类是完全二部图与树的联图;第3类是完全k(k≥3)部图与树的联图.