两类图的k-优美性

对于任意自然k，证明了G1（m1,n1;m2,n2;…;ms,ns)和G（m1,n1,m2,n2)是k－优美图，这里G1（m1,n1;m2,n2;…;ms,ns）表示由s个完全二部图Km1,n1,Km2,n2,…，Kms,ns恰有t(t≤min{m1,m2,…，ms}且这t个公共点属于每一个二部图，除此之外，任意的两个二部图无其它公共点）个公共点而无公共边所构成的图，G(m1,n1;m2,n2)是由两个完全二部图Km1,n1,Km2,n2仅有一条公共边及相关联的两个点所构成的图。     

一类二部图的奇优美性

设L为简单无向图G的一个顶点标号,L称为图G的奇优美标号,若L满足:1)L为G的顶点集V到{0,1,…,2|E|-1}的一个单射;2)由L'(e)=|L(u)-L(v)|(其中e=uv)决定的边标号L'是从G的边集E到{1,3,…,2|E|-1}的一个双射.根据奇优美图的定义,研究了一类二部图G*的奇优美标号.     

一类链图的优美性

对于由k个完全二部图K2,m1,K2,m2,…,K2,mk(其中k,n,m1,m2,…,mk为大于1的正整数)经过不同的粘接方法而得到的链图T1、链图T2、链图T5的优美性进行了研究。在此基础上对由链图T1和长为n的路Pn的一个端点粘接得到的链图T3和链图T2与长为n的路Pn的一个端点粘接得到的链图T4的优美性进行了研究。用构造的方法给出了这几类图的优美标号,得出这些图都是优美图。这样将m1,m2,…,mk的值均为2的范围扩大到大于1的正整数,从而拓宽了优美图及其应用的道路。最后提出了将链图T1、T2、T3、T4、T5分别首尾粘接而得到的一些图是优美图的猜想。     

一种证明(k,d)-强优美树的新方法

在现有研究的很多图优美问题中,发现了一种叫做悬挂和拆分的新方法.利用此新方法可以构造出较大规模的具有(k,d)-强优美标号,并证明了新方法所构造出的(k,d)-强优美树的正确性,且由(k,d)-强优美标号可导出强奇优美标号.此新方法较易转化为优良的算法,为(k,d)-强优美标号应用于网络提供了可行的理论保证.     

二部图半群和完全二部图半群

讨论了二部图半群和完全二部图半群的一些性质,探讨了二部图半群与二部图、完全二部图半群与完全二部图的关系,给出了二部图半群的圈特征。     

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

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

完全图的k—优美性与优美数

在k-优美图、k-GL矩阵（k为非负整数）的基础上，提出优美数和子段的概念，用子段计算的方法，证得了Kn(n≥5）非优美图，又证得Kn(n≥6）非1－优美图。并推出Kn的k－优美标号的性质及某些优美数。     

基于含圈非连通图优美性的拓扑图密码

图的标号是图论的一个重要分支,从非连通图入手,证明了两类非连通图■和■都具有优美标号.且证明方法能够算法化,为非连通图应用于网络提供了可行的理论保证.     

部分完全二部图与完全三部图的厚度关系

图的厚度是指将该图分解为平面生成子图的最小数,它是衡量一个图可平面性的关键指标之一,研究一个图的厚度至关重要,在超大规模集成电路和网络设计中有着重要应用.在已知的一部分图类的厚度的精确值结果的基础上,研究了部分完全二部图与完全三部图的厚度关系,得到了 K_1,n,n+1与 K_n+1,n+1、K_1,n,n+2与K_n+1,n+2、K_2,n,n+2与 K_n+2,n+2 厚度相等的结果.     

任意n个完备二分图的并图的优美性

优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了任意n个完备二分图的并图是优美图,且是交错图.     

完全二部图的拓扑指数

图的拓扑指数是应用图论中研究的主要课题之一,在信息科学、物理和化学中有着重要的应用。基于顶点度、特征值、距离的完全二部图的几类拓扑指数被研究,并给出了准确值。     

关于完全二分图的整和数的研究

提出了正整数的真ｒ－剖分的定义并利用它解决了１９９４ 年Ｆ．Ｈａｒａｒｙ 在［３］中提出的一个未决问题,即确定完全二分图Ｋｒ,ｓ的整和数和和数．得到如下结果：σ（Ｋｒ,ｓ）＝ ζ（Ｋｒ,ｓ）＝ ｓｋ＋ ｒ－ １,其中ｓｒ２,ｓｋ 是整数ｓ的真ｒ－剖分的最末项。此外,在这篇文章中我们还举例说明了Ｎ．Ｈａｒｔｓｆｉｅｌｄ和Ｓｍ ｙｔｈ 在［１１］中给出的一个结论σ（Ｋｒ,ｓ）＝ ［（３ｒ＋ ｓ－ ２）／２］是错误的。     

一类二部图的(d,1)-全标号

图G的一个k-(d,1)-全标号是一个映射f:V(G)∪E(G)→｛0,1,2…,k｝,使得(1) 相邻的顶点标不同的号;(2) 相邻的边标不同的号;(3) 顶点与所关联的边标号数相差至少为d (d≥2)。图G的(d,1)-全标号数定义为G有一个k-(d,1)-全标号的最小的k值。给出了一类二部图的(d,1)-全标号数。     

任意图的弱优美性

首先证明了完全图Ｋｎ的弱优美性，并由此证明了所有的图都是弱优美图，最后给出了弱优美图定义的改进。     

二部图上的K1,m划分问题

 考虑了二部图上的|V|-K_1,m划分问题.首先利用网络最大流与网络最小费用流算法给出了赋权二部图上该问题的1个多项式算法,然后证明了:不考虑二部图上的权重或w是一固定常数时,该算法的复杂度为O((|V|+|U|)³.最后证明了:赋权二部图上最小最大|V|-K_1,m划分问题是NP-难的.     

图F(t)m的k-强优美性

文章通过对图F(t)m的k-强优美性研究,利用k-强优美图的定义,给出对任意自然数t≥1,m≥2,当k=[m/2]时,F(t)m是k-强优美图,非连通图F(t)m∪Gk-1是优美图.当m≥2p+2时,非连通图F(t)m∪Kn,p是优美图,其中,Fm是有m+1个顶点的扇形图,F(t)m是合并t个扇Fm,F2m,…,F2t-1m的中心顶点构成的连通图,Gk-1是有k-1条边的优美图.     

偶圈冠图r-C_n的奇优美性及奇优美性算法

图G的一个奇优美标号是指存在一个双射函数L:V(G)→{0,1,2,…,2|E|-1}使得任意边e=uv∈E(G),由L′(e)=|L(u)-L(v)|决定的边标号L′为E(G)到{1,3,…,2|E|-1}的双射。根据奇优美图的定义,文章讨论了偶圈冠图r-Cn的奇优美标号问题,证明了当n≡0(mod 4)时,偶圈冠图r-Cn是奇优美图,给出的新奇优美标号算法不同于现有的文献结果。     

完全多部图的M(5)性质

针对完全多部图的唯一列表染色问题进行了研究，证明了对任意正整数n，图K1＊7，n，K1＊n，7都具有M（5）性质。