树的优美标号

1963年,G·Ringel 提出“所有树都是优美图”的著名猜想。它是图论中迄今尚未解决的难题之一。本文把树看成若干个“星”的串接和并接,从结构上对树的优美标号进行了探讨,对相当广泛的树类,给出了它们的优美标号。     

一类强优美标号树

通过依次给具有二分优美标号的树的每个顶点连续添加两次悬挂点, 运用拆分的方式, 有效证明了一类超级对虾树S(P_2m)(其中m为任意正整数)为强优美树, 该方法称为悬挂拆分法.     

关于树的二分优美标号

已知树的二分优美标号可以得到一些逼近优美树猜想的结果.给出了树的二分优美标号定义,发现了一类非二分优美树,得到了一些构造大型二分优美树的方法.定义了树的k-二分优美,并且对自然数k p2-1证明了任何顶点的优美树都是k-二分优美的.     

完全二分树的优美标号

1963年,G. Ringel猜想:所有的树都是优美树,这是图论中一个很难的问题,至今还未解决,所以数学工作者常提出一些特殊情况,要求进行验证。1976年,I. Cahit在《美国数学月刊》上,要求读者对于完全二分树进行验证,这就是具有广泛影响的Cahit问题。这个问题在1978年获得解决,实际上,这个问题早在1973年就已经被R. G. Stanton and C. R. Zarnke所解决。     

关于香蕉树的奇优美标号

在图论的研究中,图的标号问题是在二十世纪六十年代提出的 ,人们根据应用的需要提出了许多关于简单图的标号猜想.在猜想和实际应用中,涉及到最多的是树.Chen et al定义了香蕉树,在此讨论了该树的奇优美标号以及在一些情况下的伪优美标号.     

某些树的标号图及优美标号

本文引入标号图的概念,并用标号图方便地写出了一些树类的优美标号。     

两类大龙虾树的优美标号

对于J.C.Bermond提出的“所有龙虾树都优美”的猜想,目前已有不少结果(如[1]、[3]、[4]).本文则对两类大龙虾树给出其优美标号。     

一种特殊龙虾树的优美标号

六十年代初,Ringel提出的“所有的树都是优美的”猜想引起了广泛的兴趣。虽然问题迄今还没有完满的结果,但人们或从树的顶点数,或从树的边数,或从树的结构等几个方面,对一些树进行了研究,並获得了一些结果。本文就J.C.Bermond提出的“所有龙虾树都是优美的”猜想,给出一种特殊龙虾树的优美标号。单克云、庄肃钦给出的几个有优美标号的龙虾树是我们的结果的特例。从树的结构上易见。[2]中的几种树都是本文给出的树     

关于几种特殊树的优美标号

对于树,A.Rosa有一个猜想:所有的树都是优美的。本文就几种特殊的树给出了优美标号。定义如果一棵树的奇数度顶点不超过两个,则称此树为路。定理1 一切路都是优美的。证明如图一所示:     

关于几种特殊龙虾树的优美标号

对于龙虾树(lolster)J.C.Bermond提出了下面的猜想:所有的龙虾树都是优美的。本文就几种特殊的龙虾树给出优美标号。定义:设p是龙虾树L的路,若d(v)>1,v(?)V(p),与v关联的边的全体组成的子图叫做L的一个花。     

关于毛虫树的超边优美标号的一点注记

基于所有奇数阶的树都是超边优美的猜想,验证了在一些条件下,毛虫树是超边优美的,并设计了一种可构造毛虫树超边优美标号的方法.     

优美图所有优美标号的生成算法

给出了由n条边生成的所有优美图的所有优美标号的生成算法,并把代数理论和计算机工具引入了优美图的研究.利用该算法,可以根据需要得到优美图及其优美标号.     

一类蜘蛛树的(k,d)-优美标号

(k,d)-优美标号因为参数k,d可以取很多值,从而使得一些优美图是(k,d)-优美标号的特例.本文给出了(k,d)-优美标号的概念,定义了T(n+1,m)-蜘蛛树,并证明了T(n+1,m)-蜘蛛树不同情形下的(k,d)-优美标号.     

2类优美图的冠的优美标号

优美图是图论中重要的研究课题之一,有着广泛的应用价值和研究前景。但是目前仍然很难从理论上对一般图的优美性进行研究。马克杰猜想:所有优美图的冠都是优美图。这一猜想至今没有被证明或否定。对任何正整数m和n,用构造的方法给出了图I(1-Fm,4)和I(K1,1,1,n)的优美标号,从而证明了I(1-Fm,4)和I(K1,1,1,n)都是优美图。     

一类对称图的优美标号

根据优美图的定义,构造出一种图形并证明了它的优美性,利用构造性的方法对其进行优美标号。     

两类图的优美标号

设T为优美树，我们证明了T∨K2的冠及T∨K1的r－冠都是优美图。由此推广了原有的结果。     

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))都是优美图.     

两类图的优美标号

设T为优美树，我们证明了TVK2的冠及TVK1的r—冠都是优美图．由此推广了原有的结果．     

几类并图的优美标号

 对非连通并图的优美性进行了研究,给出了几类非连通的并图,得出了如下结果：对任意的正整数n,m,设s是不超过n/2的最大整数,P_n是n个顶点的路,St(m)是m+1个顶点的星形树,路P₂的补图与路P_n的联图记为A_n,则当n≥2时,A_2n与任意一个具有n-1条边的优美图的并图是一个优美图;当n≥5,m≥s+2时,A_n与星形树St(m)的并图是一个优美图,从而A_n与星形树St(n)的并图是一个优美图;当n≥5时,A_n与任意一条路P_n的并图是一个(n－s)-优美图。