一类链图的优美性

对于由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分别首尾粘接而得到的一些图是优美图的猜想。     

2类包含K4的优美图及其注记

利用计算机为辅助工具,分别给出了2类包含图K4的图K4+Gn+1和K4+Kn,n的优美标号,从而证明了图K4+Gn+1和K4+Kn,n是优美图,并由K4+Kn,n的优美性给出了边数为m的极小优美图的顶点数f(m)的范图是{(1+√8m+1)/2}≤f(m)≤{2(√m+3-1)).     

关于P_m×P_n的K-优美性

本文对 P_m×P_n 图的顶点 X_(ij)(i=1,2,…,m,j=1,2,…,n)作出标号:(i=1,2,…,m;j=2,3,…,n)式中,t=m(n—1)+n(m—1)+k—1。同时,证明了 P_m×P_n 图是 K优美的。因此,Gracl 猜想成为本文的特例而被证实。     

全图的优美性研究

本文研究完全图、完全多部图的优美性,主要得到以下结论：完全图Kn是优美图的充要条件是该图的顶点数不超过4,完全多部图K1,m,n、K2,m,n都存在优美标号算法,从而说明它们都是优美图等．     

关于一类树的优美性

在n阶树用0,1,2,…,n-1,不同的n个数对顶点标号,使得每一条边的标号也不相同(相关联一对顶点的标号差的绝对值不相同),即{1,2,…,n},称这种标号是优美标号;根据优美图的定义,研究了优美树问题中,Rosa猜想树是优美树;本文研究了一类树T_(k_3)~1,的优美性。     

关于k-优美图一个猜想的证明

二分图是一类有着广泛应用的图,但这类图并不都是优美图,因此需要进一步深入研究它的优美性。本文根据马克杰教授提出的猜想:完备二分图Km,n的冠是k-优美图(m≤n,k≥2),利用构造法证明了当m=1或m=2,k≥2时,猜想成立;当m≥3,k≥(m-2)(n-1)时,猜想成立。拓展了k-优美性的研究范围。     

三类特殊图的优美性

用构造的方法给出图K_4-P(n,2),K_3-P(n,2)和I(K_(1,1,n))的优美标号,并证明了图K_4-P(n,2),K_3-P(n,2)和I(K_(1,1,n))都是优美图.     

具有K条顶边齿轮图的优美性

文[1][2]中分别给出了轮图和齿轮图的优美性，本文证明了将n个具有K条边的星图TK的非悬挂点分别与齿轮图n个顶点相联所得图是优美的；从而得到文[3]中所提猜想的一个结果，     

有向图n·→C9的优美性

设→Cm表示具有m个顶点的有向圈,n·→Cm表示由仅具有一个公共顶点的n有向圈→Cm组成的有向图.1994年杜之亭,孙惠泉在证明了n·→C2p(n≡0(mod2))是优美图的基础上提出猜想"n·C2p+1(n≡0(mod2))是优美的",之后,很多学者在这方面做了大量的工作,并分别证明了猜想对于P=1,2,3是成立的.本文证明了猜想对于p=4(即有向图n·→C9(n≡0(mod2))也是成立的,并且给出了三种不同的优美标号.猜想对于任意正整数p是否成立,仍然是个公开问题.     

关于p_n~2优美性的研究

研究了形如p(n1,n2,…,nm)∪p2n不交并图的优美性.证明了如果T.Gracl猜想成立,则形如p(n1,n2,…,nm)∪p2n不交并图的优美性在一定的条件下成立,并给出了当n=3,4,5,6,7,8,9时,p(n1,n2,…,nm)∪p2n的优美标号.     

一类图(C)2n的优美性

给出了图(C)2n的定义,并对其优美标号进行研究,得到了当n=4k+1(k≥1)时,图(C)2n是优美图的结论.     

3类图的优美标号

用构造的方法给出图1-3n-K3,P(n,2,n-1)和I(K_(1,1,n))的优美标号,从而证明了1-3n-K_3,P(n,2,n-1)和I(K_(1,1,n))都是优美图.     

有向图n·■_9的优美性

设Cm表示具有m个顶点的有向圈,n·Cm表示由仅具有一个公共顶点的n有向圈Cm组成的有向图.1994年杜之亭,孙惠泉在证明了n·C2p(n≡0(mod2))是优美图的基础上提出猜想"n·C2p+1(n≡0(mod2))是优美的",之后,很多学者在这方面做了大量的工作,并分别证明了猜想对于p=1,2,3是成立的.本文证明了猜想对于p=4(即有向图n·C9(n≡0(mod2))也是成立的,并且给出了三种不同的优美标号.猜想对于任意正整数p是否成立,仍然是个公开问题.     

由4－圈构成的两类图的优美标号

优美图是图论中重要的研究课题之一,有着广泛的应用价值和研究前景.但是目前仍然很难从理论上对一般图的优美性进行研究.用构造的方法给出了图m－∧C4,n和m－∧C4,n＋En(m＋1)的优美标号,证明了m－∧C4,n和m－∧C4,n＋En(m＋1)都是优美图.     

一类图C_n~2的优美性

给出了图Cn2的定义,并对其优美标号进行研究,得到了当n=4k+1(k≥1)时,图Cn2是优美图的结论。     

两类图及其冠的优美标号

用构造法对两类图和两类图的冠的优美性进行了研究,得到了如下结论:对任意正整数m和n,设E_m和P_n分别是m个顶点的空图和有n+1个顶点的路,那么完全3部图K_(1,m,n),I(K_(1,m,2)),联图E_m∨P_n和I(E_2∨P_(2n))都是优美图.     

几类和扇有关图的优美性

证明下面的结论:对任意自然数n≥2,图(K_1∨(P_n∪P_(n+1)))是(n-1)-强优美图.对任意自然数n≥3,图(K_1∨P_n~((1))∪P_n~((2))))∪G是优美图;对任意自然数n≥4,图(K _1∨(P_n~((1))∪P_n~((2))∪P_n~((3)))∪H是优美图,其中k=[n/2].P_n是n个顶点的路,G_i为含有i条边的优美图.给定优美图G_(n-1)和其优美标号f,G_(k-1)和其优美标号g,设u∈G_(n-1),v∈G_(k-1)且f(u)=g(v)=0,取不同的两边xy和x′y′,点x与u合并后得到的图记为G,点x′与v合并后得到的图记为H.     

有向图n·C9^→的优美性

设→Cm表示具有m个顶点的有向圈,n·→Cm表示由仅具有一个公共顶点的n有向圈→Cm组成的有向图.1994年杜之亭,孙惠泉在证明了n·→C2p(n≡0(mod2))是优美图的基础上提出猜想"n·C2p+1(n≡0(mod2))是优美的",之后,很多学者在这方面做了大量的工作,并分别证明了猜想对于P=1,2,3是成立的.本文证明了猜想对于p=4(即有向图n·→C9(n≡0(mod2))也是成立的,并且给出了三种不同的优美标号.猜想对于任意正整数p是否成立,仍然是个公开问题.     

图C~2_n的优美性

给出了图C2n的定义,并对其优美标号进行研究,得到了当n=4k(k≥2)时图C2n是优美图的结论。     

两类非连通图优美性的研究

给出了两类非连通图(K2〖TX-〗∨Cn)∪[DD(]3[]i=1[DD)]St(mi)和(K2〖TX-〗∨C2n+k)∪St(m)∪G(k)n-1(k=1,2), 并证明了如下结论:对自然数n, m, m1, m2, m3, 设s=〖JB(［〗〖SX(〗n〖〗2〖SX)〗〖JB)］〗, n≥9, m1≥s+2, 则图(K2〖TX-〗∨Cn)∪[DD(]3[]i=1[DD)]St(mi)是一个优美图; 对 k=1,2,设n, m≥3, G(k)n-1是一个具有n-1条边的k-优美图,则图(K2〖TX-〗∨C2n+k)∪St(m)∪G(k)n-1是一个优美图。 其中,K2是一个具有2个顶点的完全图,K2〖TX-〗是图K2的补图,K2〖TX-〗∨Cn是图K2和n圈Cn的联图, St(m)是一个具有m+1个顶点的星形树。