共查询到20条相似文献,搜索用时 0 毫秒
1.
给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2. 相似文献
2.
朱海洋 《宝鸡文理学院学报(自然科学版)》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)的可达界。 相似文献
3.
4.
张苏梅 《济南大学学报(自然科学版)》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。 相似文献
5.
一个图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)-标号数. 相似文献
6.
令λ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的猜想成立. 相似文献
7.
对于正整数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. 相似文献
8.
高度平面图的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. 此猜想对高度平面图是正确的. 相似文献
9.
给出了图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. 相似文献
10.
本文给出了图G的一个非正常(r,s,t)-(p,1)-全标号的定义,该标号基于图G的(p,1)-全标号,允许有破坏此限制条件的顶点和边.非正常(r,s,t)-(p,1)-全标号的跨度是指两个标号差的最大值.图G的非正常(r,s,t)-(p,1)-全标号的最小跨度称为图G的非正常(r,s,t)-(p,1)-全标号数,记作λT(r,s,t)(G;p,1).这里主要给出了某些特殊图类的非正常(2,2,0)-(p,1)-全标号的上界. 相似文献
11.
无爪图与分裂图的L(d,1)-T标号 总被引:1,自引:0,他引:1
给定一个简单连通图G及其一棵支撑树T,图G的1个L(d,1)-T标号即一个标号函数g满足:①G的任意2个相邻点的标号至少差1;②T上任意两个相邻点的标号至少差d;③G上任意两个距离为2的点的标号至少差1.本文研究了无爪图与分裂图的L(d,1)-T标号并给出了Tld,T(G)一个界. 相似文献
12.
Mycielski图的L(2,1)-标号 总被引:3,自引:0,他引:3
设μ(G)表示一个图G的Mycielski图,λ(G)为G的L(2,1)-标号数.给出了λ(μ(G))的上、下界和λ(μ(G))达到下界(|G| 1)的一个充分条件. 相似文献
13.
张小玲 《厦门大学学报(自然科学版)》2022,(4):694-696
图G的L(3,2,1)-标号是指从顶点集V(G)到非负整数集Z*的一个映射f,满足:对于任意两个不同顶点u和v,若d(u,v)=i(i=1,2,3),则|f(u)-f(v)|≥4-i.若图G的一个L(3,2,1)-标号中的所有像元素都不超过整数k,则称之为图G的k-L(3,2,1)-标号.图G的L(3,2,1)标号数,记作λ3,2,1(G),是使得图G存在k-L(3,2,1)-标号的最小整数k.本文确定了完全最大度不小于4的毛毛虫树的L(3,2,1)标号数. 相似文献
14.
令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.这一结论改进了有关文献的相关结果. 相似文献
15.
图G的顶点集到非负整数集的一个映射f满足:对任意的x,y∈V(G),当dG(x,y)=1时,有|f(x)-f(y)|≥d;当dG(x,y)=2时,有|f(x)-f(y)|≥1。图的一个k—L(d,1)-标号是指图的一个标号L(d,1)使得min{f(v)|v∈V(G)}=k,标号数简记为λd(G)。研究了广义的Petersen图的标号L(d,1),给出一个特殊的标号方法,得到了广义的Petersen图的标号数λd(G)≤4d。 相似文献
16.
刘秀丽 《江南大学学报(自然科学版)》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)-全标号数。 相似文献
17.
研究外平面图G的L(d,1)-标号问题,证明了外平面图的L(d,1)-标号数满足:Ad≤△+2(2d—1)。对于L(d,1)-标号问题有一著名猜想:对最大度为△的任意图有A(G)≤△^2,本论文证明了此猜想对外平面图是正确的。 相似文献
18.
给定图G和正整数d,图G的L(d,1)标号是指从图G的顶点集到非负整数集的一个映射f满足:对任意的x,y∈V(G),当dG(x,y)=1时,有|f(x)-f(y)|≥d;当dG(x,y)=2时,有|f(x)-f(y)|≥1。图G的L(d,1)标号数λd(G)是指最小的正整数k使得G有一个L(d,1)标号f满足f(V){0,1,2,…,k}。已知对于最大度为Δ的一般图有λd(G)≤Δ2 (d-1)Δ。讨论了Halin图的L(d,1)标号问题,证明了λd(G)≤Δ 3(2d-1)。 相似文献
19.
设G为任意简单图,v∈V(G),把G拷贝m次,然后把拷贝后的m个v连成圈,所得到的新图记为Cm·G(v).本文给出了两类特殊的图Cm·G的(p,1)-全标号. 相似文献
20.
利用欧拉公式和权转移规则,证明了:若G为不含4,5,6-圈和2个相交三角形且满足Δ(G)≤4的平面图,则L(p,q)-标号数的上界为(2q-1)Δ(G)+6p+2q-4. 相似文献