最大度至多为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)-标号(英文)

证明了若G为不含4,5,6-圈的平面图,则λp,q(G)≤(2q-1)Δ(G)+6p+6q-6.这一结果暗含着对于Δ(G)≥12且不含4,5,6-圈的平面图G,χ(G2)≤3Δ(G)/2+1成立.因此对于这样一类图部分地证实了Wegner猜想.

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

令p≥q是两个正整数.用Δ(G)和λp,q(G)分别记平面图G的最大度和L(p,q)-标号数.文章证明了若G为不含i-圈,4≤i≤9的平面图,则λp,q(G)≤(2q-1)Δ(G)+8p-4.这一结果推出χ(G2)≤Δ(G)+5.因此对于这样一类图部分地证实了Wegner的猜想[2].

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

主要研究了一类Fullerene图Fm的L(2,1)-标号问题及L(1,1)-标号问题,给出了Fm的L(2,1)-标号数和L(1,1)-标号数的上界分别为7和6.该结果验证了Georges和Mauro猜想与Wegner猜想对于Fullerene图Fm均成立.

两个完全图的匹配和的L(p,q)-标号

设p,q为两个非负整数,一个图G的L(p,q)-标号是一个从G的顶点集V(G)到一个非负整数集的映射f,使得对于G中的任意两个顶点u,v,当d(u,v)=1时,|f(u)-f(v)|≥p;当d(u,v)=2时,|f(u)-f(v)|≥q;根据p,q之间的关系,给出两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的上界.而当q≤p≤2q时,确定了两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的准确值.

不含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.这一结论改进了有关文献的相关结果.

图的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)的可达界。

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。

平面图的距离2标号（英文）

本文证明若G为?(G)≥6且不含4,5,6,7圈的平面图,则λ_(p,q)(G)≤(2q-1)?(G)+8p-4.这一结果暗含着对于?(G)≥6且不含4,5,6,7圈的平面图G,Wegner猜想成立.

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

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

围长至少为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,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的猜想成立。

关于图的(d,1)-全标号

给出了星图、树图和均衡完全三部图的(d,1)-全数。