最大度是3的2-连通外平面图的（p，1）-全标号

图G的一个(p,1)-全标号是与频率分配有关的一种染色,它是从V(G)∪E(G)到一个整数集合的映射,必须满足:(1)图G的任意两个相邻的顶点得到不同的整数;(2)图G的任意两个相邻的边得到不同的整数;(3)图G的任意一个顶点和它所关联的边得到的整数必须至少相差p.一个(p,1)-全标号的跨度是指最大标号数与最小标号数的差.图G的所有(p,1)-全标号中最小的跨度,称为图G的(p,1)-全标号数,记为λpT(G).本文研究了最大度是3的2-连通外平面图G的全标号数.     

图的最大度与（p,1）-全标号

图G的一个(p,1)全标号是与频道分配有关的一种染色,它是从V(G)UE(G)到一个整数集合的映射,且满足:1)图G的任意两个相邻的顶点得到不同的整数;2)图G的任意两个相邻的边得到不同的整数;3)图G的任意一个顶点和它所关联的边得到的整数必须至少相差P.一个(p,1)一全标号的跨度是指最大标号数与最小标号数的差.图G的所有(P,1)-全标号函数中最小的跨度,称为图G的(p,1)-全标号数,记为λTP(G).本文我们证明了对任意的图G,其最大度△是偶的且至少是10,则λT2≤2△-1.另外对于任意的简单连通图G,其最大度为△,如果G的最大度点的邻点中至多有△-1个最大度点,则λTP(G)≤p+4.     

路圈Cartesian积的局部替换图的L(1,1,1)-标号

图G的一个L(1,1,1)-标号就是从顶点集V(G)到非负整数集的一个映射f,使得当d(u,v)=1,2,3时,都有|f(u)-f(v)|≥1.不妨设0为最小标号,则称图G的所有L(1,1,1)-标号中最大跨度f(v)的最小数为图G的L(1,1,1)-标号数,记为λ_1(G).给出了一类路圈Cartesian积的局部替换图的L(1,1,1)-标号数的确切值.     

点接拟梯子的L(d,1,1)-标号

图G的L(d,1,1)-标号指的是顶点集V(G)到非负整数集的一个映射f,且当d(u,v)=1时,|f(u)-f(v)|≥d;当d(u,v)=2时,|f(u)-f(v)|≥1;当d(u,v)=3时,|f(u)-f(v)|≥1。不妨假设最小的标号为0.G的L(d,1,1)-标号数λ(G)指的是G的全部L(d,1,1)-标号下的跨度max{f(v);v∈V(G)}最小值。基本上确定了点接拟梯子的L(d,1,1)-标号数。     

图的邻域限制标号问题的性质

对于一个整数k>0,图G的一个k-L1,2-标号是一个映射c:V(G)→{0,1,2…k}且满足对任意的u,v∈V(G),若d(uv)=1,则|c(u)-c(v)|≥1且对任意的u,v∈v(G),若存在w∈V(G),使得u,v∈NG(w),则|c(u)-c(v)|≥2.则使得图G有一个k-L1,2-标号的最小的正整数k称为图G的邻域限制标号数,记为L1,2(G).本文主要给出了图G的邻域限制标号问题的几个性质.     

关于M(o)bius梯的细分图的к-优美性

一个简单图G=(V,E)是к-优美的(k≥1为整数),如果存在单射 fV(G)→{0,1,2,…,| E|+k-1}使得对所有的边uv∈E(G),由f*(uv)=|∫(u)-f(v)|导出的映射 f*E(G)→{k,k+1,…,|E|+k-1}是双射.设G是简单图,在G的每相邻两顶点之间都加入一个顶点后所得到的图称为G的细分图.文章证明了Mobius梯的细分图是к-优美图.     

两类图的序列性

图G的标号指f是V(G)到整数集合的一个映射,然后边xy∈E(G)由f(x),f(y)导出标号.本文利用一类具有序列平衡标号的树的性质,通过"连结"与"粘接"方式,构造更多顶点的序列树;证明了C2n+1∨Km是序列图.     

一类空间图的顶点同伦与delta顶点同伦

C lasp-pass移动是Habiro1993年在定向链环上引入的一个局部移动的概念.研究了几乎相邻的图,得到以下结论:对于一个几乎相邻图G,若它不包含价为1的顶点,则G的空间嵌入上的任意clasp-pass移动都可通过Δ-同伦来实现.作为推论,有:设f,g:G→S3是价为3的几乎相邻图G的两个顶点同伦的嵌入,若对于任意(1;3)阶有限型A3-等价不变量φ,φ(f)=φ(g),则f和g一定是de lta顶点同伦的.     

关于Mbius梯的细分图的k-优美性

一个简单图G =(V ,E)是k 优美的 (k≥ 1为整数 ) ,如果存在单射f:　V(G)→ { 0 ,1,2 ,… ,|E| +k - 1}使得对所有的边uv∈E(G) ,由f (uv) =|f(u) -f(v) |导出的映射f :　E(G)→ {k ,k + 1,… ,|E| +k - 1}是双射 .设G是简单图 ,在G的每相邻两顶点之间都加入一个顶点后所得到的图称为G的细分图文章证明了M bius梯的细分图是k 优美图     

V_k~m-图的魔幻标号

证明了二部分Vm k-图是一个超级集有序π(-1)-边魔幻树当且仅当它是一个集有序优美树.给出了用具有超级集有序-边魔幻全标号二部分图来构造大的具有超级集有序-边魔幻全标号的图,得到了优美、超级集有序-边魔幻等标号的对偶标号以及关于超级集有序-边魔幻全标号的几个结果.     

关于柱图Cλ(Pn)的细分图的k-优美性

一个简单图G=(V,E)是k-优美的(k≥1为整数),如果存在单射f:V(G)→{0,1,2,…,｜E｜+k-1}使得对所有的边uv∈E(G),由f*(uv)=｜f(u)-f(v)｜导出的映射f*:E(G)→{k,k+1,…,｜E｜+k-1}是双射.若G是简单图,且在G的所有相邻的两个顶点之间都加入一个顶点,则所得到的图称为G的细分图,该文证明了当λ≥2,n≡0(mod2)时,Cλ(Pn)的细分图Cλ(Pn)是k-优美图.     

基于书图的计算机无线网络的代码分配

把一些计算机无线网络抽象概括为书图,并利用书图的L(1,d)-标号问题模拟一些计算机无线网络的代码分配问题.针对书图的L(1,d)-标号问题(d≥2)展开研究,来确定计算机无线网络的最优代码数及其分配方案.给出了书图的L(1,d)-标号函数,确定了书图的L(1,d)-标号数的上界,另外,根据书图的性质以及结构特征,确定了书图的L(1,d)-标号数的下界,得到书图的L(1,d)-标号数.     

关于积图Ps×Ct的细分图的K-优美性

该文定义:一个简单图G=（V,E）是k-优美的（k≥1为整数）,如果存在单射f:V（G）→{0,1,2,…,|E| k-1}使得对所有的边uv∈E（G）,由f＊（VV）一丫（V）-/（V门导出的映射 f＊:E（G）→{k,k 1,…,|E| k-1}是双射。若G是简单图,且在G的所有相邻的两个顶点之间都加入一个顶点,则所得到的图称为G的细分图。该文还证明了积图Pn×C2m、P2n×C2m 1、P2n×Cm的细分图是k-优美图。     

不含4-圈和7-圈的平面图的列表均匀染色

任意给定图G的一个k-一致列表L,若G是L-可染的,且满足每种颜色至多在「|V(G)|k﹁个点上出现,则称G是k-均匀可选择的.若图G有一个正常k-顶点染色满足任2个色类中的顶点数至多相差1,则称G是k-均匀可染的.应用d ischarge方法,讨论了不含4-圈和7-圈的平面图的结构.证明了对于不含4-圈和7-圈的平面图G,当k≥m ax{Δ(G),8}时,G是k-均匀可选择的,同时,G也是k-均匀可染的.     

路的中间图的最优pebbling数

图G上的一个pebbling移动是从一个顶点移走两个pebble,把其中的一个pebble移到与其相邻的一个顶点上．图G的最优pebbling数fopf（G）是最小的正整数,使得把n个pebble恰当地放置在G的顶点上,总可以通过一系列pebbling移动把一个pebble移到任何一个指定的顶点上．本文给出了路的中间图M（Pa）的最优pebbling数．     

3-连通图支撑树上的可去边数

设e是3-连通图G的一条边,若G-e是某个3-连通图的部分图,则称e是G的可去边.我们对3-连通图G的支撑树上可去边数进行了研究,给出了"阶至少为6且最小度为4(或围长至少为4)的3-连通图G的支撑树上的可去边数至少为2"的简化证明,证明了3-连通3正则图的支撑树上至少有2条可去边.     

一类双圈图中具有最大、最小Wiener指数的图

设G=(V,E)是一个连通图,C的Wiener指数W(G)是指图G中所有顶点对之间的距离之和,即W(G)= ∑∣u,v∣(∈) GdG(u,v).B(n)表示具有n个顶点和n 1条边的简单连通双圈图的集合,B1(n)表示B(n)中圈之间没有公共边的双圈图的集合.刻画了B(n)和B1(n)中具有最小Wiener指数和具有最六Wiener指数的极图的特征.     

关于图的色数与厚度的一些新结果

设V(G)是图G的顶点集,p=︱V(G)︱是图G的顶点数,X(G)是图G的顶点染色数,θ(G)是图G的厚度,︱S︱为图G最大团的顶点数.证明了在三种情况:(1)若图G是完全图;(2)︱S︱=p-1;(3)︱S︱=p-2下,皆有X(G)≤4θ(G)+θ2(G)-1.     

中间图的邻点可区别全染色

设G是简单连通图，G的庀．正常全染色f称为是邻点可区别的，如果对G的任意相邻的两顶点，其点的颜色及关联边的颜色构成的集合不同，称f为G的k-邻点可区别全染色．这样的后中最小者称为G的邻点可区别全色数．本文考虑了图的中间图的邻点可区别全色数，并确定了路、圈、星图和扇图的中间图的邻点可区别全色数．     

一类双图图中具有最大、最小Wiener指数的图

设G=（V,E）是一个连通图,G的Wiener指数W（G）是指图G中所有顶点对之间的距离之和,即W（G）=∑{u,v}GdG（u,v）.B（n）表示具有n个顶点和n＋1条边的简单连通双圈图的集合,B1（n）表示B（n）中圈之间没有公共边的双圈图的集合.刻画了B（n）和B1（n）中具有最小Wiener指数和具有最大Wiener指数的极图的特征.