共查询到20条相似文献,搜索用时 15 毫秒
1.
令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的猜想成立。 相似文献
2.
对于正整数p,q,n与图G,如果函数φ:V(G)→{0,1,2, ,n}满足如下关系:若distG(u,v)=1,则|φ(u)-φ(v)|≥p;若distG(u,v)=2则|φ(u)-φ(v)|≥q,那么称函数φ为图G的L(p,q) 标号.在所有L(p,q) 标号中最小的n称为(p,q) 跨度,记作λ(G;p,q).本文证明了如下结论:设图G是一个最大度为Δ的外部平面图,那么λ(G;p,q)≤qΔ+4p+2q-4. 相似文献
3.
高度平面图的L(p,q)—标号 总被引:1,自引:0,他引:1
研究高度平面图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. 此猜想对高度平面图是正确的. 相似文献
4.
令λ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的猜想成立. 相似文献
5.
令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.这一结论改进了有关文献的相关结果. 相似文献
6.
利用欧拉公式和权转移规则,证明了:若G为不含4,5,6-圈和2个相交三角形且满足Δ(G)≤4的平面图,则L(p,q)-标号数的上界为(2q-1)Δ(G)+6p+2q-4. 相似文献
7.
朱海洋 《宝鸡文理学院学报(自然科学版)》2006,26(1):23-27
令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)的可达界。 相似文献
8.
张苏梅 《济南大学学报(自然科学版)》2007,21(4):311-313
图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。 相似文献
9.
研究外平面图G的L(d,1)-标号问题,证明了外平面图的L(d,1)-标号数满足:Ad≤△+2(2d—1)。对于L(d,1)-标号问题有一著名猜想:对最大度为△的任意图有A(G)≤△^2,本论文证明了此猜想对外平面图是正确的。 相似文献
10.
11.
如果平面图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. 相似文献
12.
本文将距离为2的点的限制条件放松到支撑树上,提出了一类新的点标号问题,并相应给出了这种标号数的一般上界。 相似文献
13.
一个平面图被称为 2-外平面图,如果它能嵌入平面使得所有顶点出现在至多2个面的边界上.主要研究了2-外平面图的L(2,1)-标号,得到:若图G是一个2-外平面图,则λ(G)≤Δ(G)+12,其中Δ(G)表示G的最大度. 相似文献
14.
本文研究了围长至少为5的平面图的线性着色问题。利用反证法,通过分析最小反例图的结构,运用欧拉公式结合适当的权转移规则得出矛盾,从而证明了围长至少为5的平面图的线性色数满足lc(G)≤[△(G)/2]+4,改进了这方面的结果。 相似文献
15.
刘秀丽 《江南大学学报(自然科学版)》2011,10(6):749-752
研究了与频道分配有关的一种染色问题——(p,1)-全标号。(p,1)-全标号是从V(G)∪E(G)到集合{0,1,…,k}的一个映射,满足:G的任两个相邻的顶点得到不同的整数;G的任两个相邻的边得到不同的整数;任一个点和与它相关联的边得到的整数至少相差p。称最小的数k为图G的(p,1)-全标号数。根据所构造图的特征,利用穷染法,得到了这些图的(2,1)-全标号数。 相似文献
16.
给出了图L(d,1,1)-标号的一般性质. 对一般图G, 给出了构造L(d,1,1)-标号的一个算法, 证明了λd,1,1(G)≤Δ3-Δ2+dΔ. 对最大度Δ的树T, 证明了d+Δ-1≤λd,1,1(T)≤d+2Δ-2, 并且式中的上界与下界都是可达的. 此外, 对于两类特殊的树图: 拟正则树TΔ及正则毛毛虫Catn, 给出了确切的L(d,1,1)-标号数, 其中d≥2. 相似文献
17.
通过找出图G的补图Gc的路覆盖数与其子图G-S的各个连通分支补图的路覆盖数间的关系, 在图G的λ数与其补图Gc的路覆盖数之间关系的基础上, 给出图G的λ数与子图G-S的各个连通分支补图的路覆盖数之间的关系(这里S是G的一个k顶点割). 相似文献
18.
一个图G的L(2,1,1)-标号是指从顶点集V(G)到非负整数集的一个映射f,且使得:当d(u,v)=1时,|f(u)-f(v)|≥2;当d(u,v)=2或3时,|f(u)-f(v)|≥1.不妨假设设最小的标号为0.则,G的L(2,1,1)-标号数λ(G)是G的所有L(2,1,1)-标号下的跨度max{f(v);v∈V(G)}的最小值.完全确定了点接拟梯子的L(2,1,1)-标号数. 相似文献
19.
Mycielski图的L(2,1)-标号 总被引:3,自引:0,他引:3
设μ(G)表示一个图G的Mycielski图,λ(G)为G的L(2,1)-标号数.给出了λ(μ(G))的上、下界和λ(μ(G))达到下界(|G| 1)的一个充分条件. 相似文献
20.
图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,其中u,v是图G的顶点.不妨设最小标号为0.那么,图G的L(2,1)-标号数λ(G)是G的所有L(2,1)-标号下的跨度max{f(v);v ∈ V(G)}的最小数.本文定义了拟梯子,并完全确定了拟梯子的L(2,1)-标号数. 相似文献