两类图的L(2.1)-标号数

图G的一个L(2.1)-标号是从顶点集V(G)到非负整数的一个函数f,使得若d(u,v)=1时,有|f(u)-f(v)|≥2;若d(u,v)=2时,有|f(u)-f(v)|≥1.图G的L(2.1)-标号数λ(G)是G的所有L(2.1)-标号下的跨度max{f(v):v∈V(G)}的最小数.图Fn+1*为扇图的路上每个顶点增加一个悬挂边得到的图.图Hn为轮图的圈上每个顶点增加一个悬挂边得到的图.本文确定了图Fn+1*与Hn的L(2.1)-标号数.     

若干并图的优美标号

证明了,对任意大于1的自然数m,n,p,非连通图(■ V ■)∪K_(n,p)是优美图;当k≤p,m=kn+3或m=kn+1时,非连通图(P_2 V ■)∪K_(n,p)是优美图;当p≥2,m=3k+1时,非连通图(P_2 V ■)∪K_(3,p)是优美图;对任意正整数n,p,非连通图(P_1 V P_(2n+2))∪_(n,p)是优美图.     

有向图的距离标号边跨度

将无向图距离标号边跨度的概念引入到有向图.运用图的流（flow）及tension理论,确定了有向树和有向圈的边跨度,以及最长有向路长不超过3的有向二部图边跨度的可达上下界.     

P2r,6图的优美性

Kathiresan KM证实$P_{2r,2m-1}$($r,m$皆为任意正整数)是优美的且猜想:除了$(a,b)=(2r-1,4m-2)$外,所有的$P_{a,b}$都是优美的.杨元生证实$P_{2r+1,2m+1}$是优美的,并且证实了当$r\leq7$, $r=9$时的$P_{2r,2m}$是优美的.严谦泰证实$r$为奇数时$P_{2r,2m}$是优美的.采用回溯和分支限界算法搜索到了一个适合于所有$P_{2r,b}$图($r,b$皆为任意正整数)的优美标号,用函数构造法提取其规律并从数学的严格性进行了证明,使得所有的$P_{2r,b}$图($r,b$ 皆为任意正整数)的优美性得到了证实.     

图P_n~3的优美标号

定义了图 P3 n,证明了当 n =6 k 2及 n =6 k 4时 ,图 P3 n是优美图 ,并得到它们的优美标号 ,其中 k是任意自然数 .     

一类超图的异色数

一个超图Ｈ＝（Ｖ，Ｅ）的一个ｔ着色是从Ｖ到一个ｔ元集的满射，称Ｈ的一个ｔ着色ｆ分离Ｈ的一个条边α∈Ｅ（Ｇ）如果｜ｆ（ａ）｜＝｜α｜。称ｆ为异色的如果ｆ分离Ｈ的至和一条边，否则ｆ为非异色。Ｈ的异色数，记为ｈｃ（Ｈ），是最小的数ｔ使得任一个着色都是异色。在本文中，我们引进一类超图，并确定了它们的异色数。     

关于图P3n优美性的研究

在n个顶点的路Pn上,当且仅当两点的距离为3时增加一条边,所得的图称为P3n,本文给出了图P3n(n≥4)的优美标号,从而证明了P3n都是优美图.     

关于两类平面图及相关图的L(d1,d2)-标号问题

图G的L(2,1)标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥(2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)标号数λ(G)是使得G有max{f(v)V∈V(G)}=k的L(2,1)标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.本文将L(2,1)-标号推广到L(d1,d2)-标号,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d1,d2)-标号的上界,作为推论,本文证明了对上述几类图,有上述猜想成立.     

一类图的cordial性

A表示删除2度点后的点导出子图是空图的图形，文章的结论：A不是cordial图的充要条件是A是偶度图且e（A）=4m＋2．