两类太阳图的奇优美标号

图的标号问题起源于1966年A.Rosa的著名的优美树猜想.一个图的顶点标号是图的顶点集到整数集的映射,而边标号则是图的边集到整数集的映射.根据对映射的不同要求,产生了各种类型的图标号问题.文章给出了太阳图Sm,n的定义,用构造的方法给出了太阳图S4,n、S8,n的奇优美标号,从而证明了它们都是奇优美图.     

两类太阳图的奇优美标号

图的标号问题起源于1966年A.Rosa的著名的优美树猜想.一个图的顶点标号是图的顶点集到整数集的映射,而边标号则是图的边集到整数集的映射.根据对映射的不同要求,产生了各种类型的图标号问题.文章给出了太阳图Sm,n的定义,用构造的方法给出了太阳图S4,n、S8,n的奇优美标号,从而证明了它们都是奇优美图.     

完全二部图的边优美性

研究了完全二部图及其局部边迁移图的边优美性.主要结果有:当(m,n)=1时,奇阶完全二部图K_(m,n)为边优美图的充要条件是m+n|mn+1.     

完备二分图的冠的k-优美性

图的优美性是图的一个重要性质,有广泛的应用.马克杰猜想:完备二分图Km,n的冠I(Km,n)是k-优美图,这里m,n,k是任意正整数且m n.对于m=2,3,4,5或k>(m-1)n的情形,利用构造的方法,证明了猜想的正确性.这一结果丰富了优美图理论.     

关于图C4∪P3n的优美性

讨论了形如C4 ∪P3n非连通并图的优美性,用构造性的方法给出了C4 ∪P3n的优美标号,并证明C4 ∪ P3n是交错图.     

王冠Qn的k优美性

图的优美性是图的一个重要性质,有着广泛的应用.R.Frucht证明了:所有的王冠Qn都是优美图.对于王冠Qn的k-优美性,利用构造的方法,得到结论:当n是偶数时,王冠Qn是k-优美图;当n是奇数时,王冠Qn不是k-优美图,这里k是任一大于1的整数.这一结果丰富了优美图理论,对研究其他图类的k-优美性有参考价值.     

关于图Pm*Pn的邻点可区别全染色

设G1，G1是有限简单图，引入了图G1＊G2的概念，给出了图Pm＊Pn（n≥2，m≥2）的邻点可区别全色数 χα1（Pm＊Pn）={5,当m=n=2时；7,当m=2,n〉2或m〉2,n=2时；9，当m=n=3时；10，当m≥3，n〉3或m〉3，n≥3时。     

Pm×Pn的全色数

给出了图的一种染色方法,并证明了该染色为正常全染色,从而得到了Pm×Pn的全色数:χt(Pm×Pn)=54!mm>=22,,nn>≥22或m≥2,n=2.此结果尚未见其它文献报道.     

关于图的K-优美性

给出了图的k-优美标号的个数;得到了k-优美图的一个必要条件;研究了两类图P3n和齿轮图的k-优美性.     

R(4,5,n)型图的优美性

讨论了R(4,5,n)型图的优美性,用构造性的方法给出了R(4,5,n)型图的优美标号。证明了图R(4,5,n)是交错图。     

一个路与一个完全图的直积的L(2,1)-标号

为了得到一个路Pm与一个完全图Kn的直积Pm×Kn的L（2,1）-标号数,通过归纳猜想,分类讨论,证明了m=3或4时,Pm×K3的L（2,1）-标号数为6,m≥5时,Pm×K3的L（2,1）-标号数为7,m≥5且n≥3时,Pm×Kn的L（2,1）-标号数的上界是3n-2.     

图2C_n是优美有向图

设 2 Cn(n≥ 3 ,n∈N)表示两个不相交的有向回路Cn 组成的图 .本文证明2Cn 是优美有向图     

图T(F_(n,8),P_m)奇优美标号算法及实现

给出了图T(F_(n,8),P_m)的定义,提出了该类图的计算机标号算法,理论证明了这种算法的正确性,从而说明图T(F_(n,8),P_m)是奇优美图;最后,编制了"图T(F_(n,8),P_m)奇优美标号算法"程序,并通过大量实验数据说明利用该算法给图T(F_(n,8),P_m)进行奇优美标号是行之有效的.     

图W4k,n及其r-冠的优美性

马克杰等在文（1）中证明了p1∨p2及其r-冠是优美的，从而猜想；任意优美图的r-冠都是优美的，在此猜想指引下，本文明明了：当m=0（mod 4），Wm,n为优美图的充要条件是n=0或3（mod 4）在此之后又证明了：Wm.n当m=0（mod 4）r-冠也是优美图。     

P_n×P_m图的邻点可区别全染色和邻点强可区别全染色

对Pn×Pm图的邻点可区别全染色和邻点强可区别全染色问题进行了探讨,给出了染色数公式Xat(Pn×Pm)={4 n=m=2 5 n=2 m≥3,ast(pn×pm)=6 n≥3 n≥3{5 n=m=25 n=2 m≥3 6 n≥3 m≥3     

完全二部图的边优美性

研究了完全二部图及其局部边迁移图的边优美性,主要结果有：当(m,n)=1时,奇阶完全二部图Km,n为边优美图的充要条件是m n|mn 1。     

关于图C_3∪P_n~3的优美性

讨论了形如C3∪P3n非连通并图的优美性,用构造性的方法给出了C3∪P3n的优美标号.     

完全二部图的边优美性

研究了完全二部图及其局部边迁移图的边优美性．主要结果有：当（m,n）=1时,奇阶完全二部图K(m,n)为边优美图的充要条件是m＋n|mn＋1．     

几类图的匹配多项式及其性质

本文刻画了Pm，Cn，Q(3，n)，Q(s，t)的路树的匹配多项式，并得到了有关Pm，Cn，Q(3，n)，Q(s，t)，Ti,j,k,Ti,j,k,i,m的匹配多项式之间的一些关系，这些关系在比较这些图的最大匹配根，寻找此类图以及它们的并的匹配等价图类有重要意义．     

确定某些对虾树的优美性(英文)

众所周知,优美树猜想(GTC)自1966年Rosa提出到今天已经成为一个非常著名的未解决的问题,GTC问题最初来自于把完全图K2n+1分解成同构于任意一棵预先指定的n条边的树的2n+1个子图.尽管有大量的有关GTC的文章发表,但彻底解决这个猜想还很遥远.故而,人们把研究GTC的范围缩小到一些特定类型的树上来,如Bermond的猜想:每一棵对虾树都是优美的(1997).由此启发,我们确定了几类对虾树的优美性,并提出了几个问题以供进一步研究.