高度平面图的L(p,q)—标号

研究高度平面图G的L(p,q)-标号问题，证明了高度平面图h1-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+6(p-q)；h2-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+8p-6q-1. 对于L(2,1)标号问题Griggs和Yeh有一著名猜想：对最大度为Δ的任意图有λ(G)Δ2. 此猜想对高度平面图是正确的.     

围长至少为6的平面图的L(p,q)-标号

令λp,q(G)为图G的L(p,q)-标号数,其中p和q是正整数且p≥q.证明了若G是围长g(G)≥6的平面图,则λp,q(G)≤(2q- 1)△(G) +4p +6q-5;若G是围长g(G)≥6且△(G)≠5的平面图,则λp,q(G)≤(2q-1)△(G)+ 10p-2q-4.这一结果暗含着对于g(G)≥6且△(G)≠5的平面图G,Wegner的猜想成立.     

不含4-圈的平面图的L(p,q)-标号

令G为平面图,用Δ(G)和λp,q(G)分别表示G的最大度和L(p,q)?标号数,其中p和q是满足p≥q的两个正整数.证明了若G为Δ(G)≤5且不含4-圈的平面图,则λp,q(G)≤(2 q?1)Δ(G)+8p+1 4q?11.这一结论改进了有关文献的相关结果.     

最大度至多为4的平面图的L(p,q)-标号

利用欧拉公式和权转移规则,证明了:若G为不含4,5,6-圈和2个相交三角形且满足Δ(G)≤4的平面图,则L(p,q)-标号数的上界为(2q-1)Δ(G)+6p+2q-4.     

无4,5,6-圈且无两个相交三角形的平面图的L(p,q)-标号

令λp,q(G)为图G的L(p,q)-标号数,证明了若G是不合4,5,6-圈且不含两个相交三角形的平面图,则λp,q(G)≤(2q-1)△(G)+max｛4p +4q-4,6p +2q-4,8p-4｝.这一结果暗含着对于不合4,5,6-圈且不含两个相交三角形的平面图G,Wegner的猜想成立.     

图的L(p,q)-标号问题

令G为图,p,q为2个正整数,p≥q。G的一个L(p,q)-标号是映射f:V(G)→{0,1,2,…},使得对任意x,y∈V(G),若dG(x,y)=1则|f(x)-f(y)|≥p;若dG(x,y)=2则|f(x)-f(y)|≥q。G的一个m-L(p,q)-标号是标号f:V(G)→{0,1,2,…},使得对任意x∈V(G),有f(x)≤m。并称λp,q(G)=min{m|存在G的一个m-L(p,q)-标号}为图G的L(p,q)-数。本文给出k-退化图、G1和G2的联图G1∨G2及G1和G2的M-matched sum图G1M G2的L(p,q)-数不同上界。最后给出仙人掌图,唯一圈图L(p,1)-数λp,1(G)的可达界。     

围长至少为5的平面图的L（P，q）-标号

令Ap,q（G）为图G的L（p,g）-标号数,其中P和q是两个正整数且p≥q。证明了若G是围长g（G）≥5的平面图,则Ap,q（G）≤（2q-1）△（G）＋6p＋10q-8。由此导得对于g（G）≥5且△（G）≥16的平面图G,Wegner的猜想成立。     

Halin图的列表L(p,q)标号

图G的一个列表L,是指对G的每一个顶点v指定的一个标号集合L(v)。G的一个列表L(p,q)-标号是G的一个正常L(p,q)-标号,使得每一个顶点v∈V(G)均可在其对应的列表L(v)里选取一个标号。G的一个k-列表L(p,q)标号是一个列表L(p,q)-标号,使得G的所有顶点v的列表L(v)的长度L(v)=k 1。定义G的列表L(p,q)-标号数λl(G)=m in{G k有一个k-列表L(p,q)-标号}。讨论了Halin图的列表L(p,q)-标号问题,证明了λl(G;p,q)≤(2q-1)Δ(G) 6p-3。     

外平面图的L(d,1)-标号

研究外平面图G的L（d,1）-标号问题,证明了外平面图的L（d,1）-标号数满足：Ad≤△＋2（2d—1）。对于L（d,1）-标号问题有一著名猜想：对最大度为△的任意图有A（G）≤△^2,本论文证明了此猜想对外平面图是正确的。     

高度平面图的列表L(p,q)-标号

如果平面图G的最大度Δ(G)=|V(G)|-k, k=1,2,…,则称G为一个hk-图,k=1,2的hk-图称为高度平面图.研究了高度平面图G的列表L(p,q)-标号问题, 给出了高度平面图G的列表L(p,q)-标号数λl(G;p,q)的上界,并对h1-图证明了λl(G;p,q)≤(2q-1)Δ 6(p-q);对h2-图有λl(G;p,q)≤(2q-1)Δ 8p-6q-1.     

图的L(d,1,1)-标号

给出了图L(d,1,1)-标号的一般性质. 对一般图G, 给出了构造L(d,1,1)-标号的一个算法, 证明了λ_d,1,1(G)≤Δ³-Δ²+dΔ. 对最大度Δ的树T, 证明了d+Δ-1≤λ_d,1,1(T)≤d+2Δ-2, 并且式中的上界与下界都是可达的. 此外, 对于两类特殊的树图： 拟正则树T_Δ及正则毛毛虫Cat_n, 给出了确切的L(d,1,1)-标号数, 其中d≥2.     

外部平面图的平方图的染色

图G的平方图，记作G^2，是一个以原图的顶点集为顶点集，若原图中两点的距离不大于2则连以边所成的图．本文确定了圈的平方图的色数．对于外部平面图，得到以下结论：设G是一个最大度为△(G)的简单连通外部平面图，G≠C5．则x(G^2)≤△(G) 2．     

外平面图的完备染色

设Ｖ（Ｇ）、Ｅ（Ｇ）和Ｆ（Ｇ）分别为平面图Ｇ的点集、边集和面集。Ｇ的完备色数Ｘｃ（Ｇ）是使得Ｖ（Ｇ）∪Ｅ（Ｇ）∪Ｆ（Ｇ）中相邻或相关联的元素间均染不同色的最少颜色数。本文证明了：对无割点的外平面图Ｇ，有Ｘｃ（Ｇ）≤ｍａｘ｛７，△（Ｇ）＋１｝，其中△（Ｇ）为Ｇ的最大度数。     

关于n-格图及相关图的L(2,1)标号问题

图G的L(2，1)标号是一个从顶点集V(G)到非负整数集的函数?（x），使得若d(x，y)=1，则|?（x）-?(y)|≥2；若d(x，y)=2，则|?（x）-?(y)|≥1。移动通讯频率分配问题可转化为图的L(2，1)标号问题。将2-格图及相关图推广到n-格图及相关图，并给出了它们的L(2，1)标号。