若干图的点强全染色(英文)

对图G及正整数k，映射f：满足：（1）任意e1，e3，如果e1，e2是相邻或相关联的，则有；（2）对u，v，w（G）有，则称f为G的一个k-点强全染色，并且K|G的社点强全染色称为G的点强全色数．本文讨论了一些特殊困的点强全色数，并提出了一个猜想：若G为每一分图的阶数不小于6的图，则（G），其中（G）为本文中定义的一新参数．     

图的正常三着色的最大方法数

令F_(v,e)表示所有简单无向(v,e)-图的全体所成的集合,f(v,e,λ)=max{P(G,λ);G∈F_(v,e)}.本文改进了文献[1]中给出的f(v,e,3)的上界,并指出[1]中的猜想的充分性是不成立的.     

图的符号星k控制数

引入了图的符号星k控制的概念.设G=（V,E）是一个图,一个函数f：E→{-1,＋1},如果∑e∈E[v]f（e）≥1对于至少k个顶点v∈V（G）成立,则称f为图G的一个符号星k控制函数,其中E（v）表示G中与v点相关联的边集.图G的符号星k控制数定义为γkss（G）=min{∑e∈Ef（e）｜f为图G的符号星k控制函数}.在本文中,我们主要给出了一般图的符号星k控制数的若干下界,推广了关于符号星控制的一个结果,并确定路和圈的符号星k控制数.     

关于几类图的L(3,2,1)-标号问题

图G的L(2，1)-标号是一个从顶点集V(G)到非负整数集的函数f(x)，使得若d(z，y)=1则|f(x)-f(y)|≥2；若d(x，y)=2，则|f(x)-f(y)|≥1。图G的L(2，1)-标号数是λ(G)使得G有的max|f(v)：v∈V(G)|=κ的L(2，1)-标号中的最小数κ。本将L(2，1)-标号问题推广到更一般的情形即L(3，2，1)标号问题，并得到了平面三角剖分图、立体四面体剖分图的λ3(G)的上界。     

两类图的L(2.1)-标号数

图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.图G的L(2.1)-标号数λ(G)是G的所有L(2.1)-标号下的跨度max{f(v):v∈V(G)}的最小数.图Fn+1*为扇图的路上每个顶点增加一个悬挂边得到的图.图Hn为轮图的圈上每个顶点增加一个悬挂边得到的图.本文确定了图Fn+1*与Hn的L(2.1)-标号数.     

关于分数(g,f)-因子消去图

一个图称为分数（g,f）－因子消去图，如果去掉图G中的任何一条边e图G仍有一个分数（g,f）－因子。本文分别给出了一个力是分数1－因子消去图和分数2－因子消去图的几个充分条件，并给出一个图有一个分数（g,f）－因子不含给定对集中任何一条边的充要条件。     

点接手镯图的L(1,1,1)-标号

图的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)的最小数为图的L(1,1,1)-标号数,记为λ(G).基本给出了点接手镯图的L(1,1,1)-标号数的确切值.     

关于图的L(3,2,1)-标号问题

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) .使得若d(x ,y) =1 .则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y)｜≥ 1 .图G的L( 2 ,1 )标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .本文将L( 2 ,1 ) 标号问题推广到更一般的情形即L( 3,2 ,1 ) 标号问题 .我们首先定义了图G的顶点 3 着色及图的 3 色数 χ3 (G)等有关概念 ,并推导出 3 色数 χ3 (G)的上界 ;然后根据 χ3 (G)与λ3 (G)的关系 ,得出了对一般图G ,有λ3 (G) ≤ 3maxH Gδ(H) (Δ2 -Δ 1 )这一一般关系式 ;最后证明了对一般平面图G ,有λ3 (G)≤ 1 5(Δ2 -Δ 1 ) ,并得出了其它几类平面图的λ3 (G)的上界 .     

图的1-因子、f-因子和(g,f)-因子

设G是一个图且有一个1-因子F,g和f是定义在V（G）上的非负整数值函数且对每个X∈V(G)有g（X）＜f(X)≤dG（x）,且f(v(G))为偶数．（i）若对每个xy∈F有f(x)=f(y)且G－{x,y}有一个（g,f)-因子,则G有一个（g,f)-因子;（ii）若对每个xy∈F有f(X）=f（y）且G-{X,y}有f-因子,则G有f-因子.     

二分(mg,mf)-图中的(g,f)-因子

设G是一个二分图具有顶点集V（G）和边集E（G）。设g和f是定义在V（G）上的两个正整值函数使对任意的x∈V（G）有g(x)≤f(x)，G的一个（g,f）－因子H是G的一个生成子图满足g(x)≤dH(x)≤f(x）。若图G本身是一个（g,f）－因子，则称G是一个（g,f）－图。本文得到一个（mg,mf）－图具有特殊性质的（g,f）－因子的充分条件，从而推广了文献[6]中的一个结果。     

关于几类图的L(2,1)标号问题

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y) ｜≥ 1 .图G的L( 2 ,1 ) 标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) ≤Δ2 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 ,并证明了上述猜想对以上几类图成立     

一类多重联图的邻点可区别E-全染色

设G（V,E）是一个简单图,k是一个正整数,f是一个V（G）∪E（G）到{1,2,…,k]．的映射．如果Au,v∈E（G）,则f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,C（u）≠C（v）,其中C（u）={f（u））U{f（uv）｜uv∈E（G））．称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别B全色数．本文给出了星、路、圈间的多重联图的邻点可区别E-全色数．     

竖梯的局部替换图的L(d,1,1)-标号

图的L(d,1,1)-标号定义为顶点集V(G)到非负整数集的映射f,且当d(u,v)=1时,均有|f(u)-f(v)|≥d,当d(u,v)=2,3时,均有|f(u)-f(v)|≥1.不妨设0为最小标号,则称图G的所有L(d,1,1)-标号中的最大跨度max{f(v):v∈V(G)}的最小数为图的L(d,1,1)-标号数,记为λ_d(G).基本给出了竖梯的局部替换图的L(d,1,1)-标号数的确切值或界.     

关于图的L(d,1)-标号问题

图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)-标号数λ(G)是使得G有max{f(v)v∈V(G)}=k的L(2,1)-标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立.     

关于图的L(3,2,1)-标号问题

图 G的 L (2 ,1) -标号是一个从顶点集 V(G)到非负整数集的函数 f (x) ,使得若 d(x,y) =1,则 | f (x)- f (y) |≥ 2 :若 d(x ,y) =2 ,则 | f (x) - f (y) |≥ 1.图 G的 L (2 ,1) -标号数λ(G)是使得 G有 max{ f (v) :v∈ V(G) } =k的 L(2 ,1) -标号中的最小数 k.本文将 L(2 ,1) -标号问题推广到更一般的情形即 L(3,2 ,1) -标号问题 ,并得出了细分图、Descartes图的 λ3 (G)的上界 .     

关于图的距离标号问题

图G的L（2，1）-标号是一个从顶点V（G）集到非负整数集的函数f（x），使得若d（x，y）：1，则｜f（x）-f（y）｜≥2；若d（x，y）=2，则｜f（x）-f（y）｜≥1。图G的L（2，1）-标号数A（G）是使得G有max{f（v）：v∈V（G）}=k的L（2，1）-标号中的最小数愚。本文将L（2，1）-标号问题推广到更一般的情形即L（d1，d2，d3）-标号问题，并得出了复合图的λd1，d2，d3（G）的上界。     

分数(g,f)-因子覆盖图

一个图称为分烽（g,f)- 因子覆盖图，如果G中的任何一条边e都包含在一个分数（g,f)- 因子中，并且满足h(e)=1，其中h是分数（g,f)- 因子的导出函数。本文给出了一个图是分数（g,f)- 因子覆盖图的充要条件。     

Petersen图的Hamilton性和边色数

对简单图G(V,E),定义图G的关联图I(G)为V(I(G))={(ve)|v∈V(G)且e∈E(G)和v与e关联},E(I(G))={(ue,vf)Iu=v或e=f或uv=e或uv=f}.本文证明了Petersen图可被分解为边不交的Hamilton-圈和一个1-因子的并.     

3-调和的5-圈图

设v1，v2，v3，…，vn是图G的n个顶点，（d（v1），d（u2），d（u3），…，d（vn））^T是图G邻接矩阵A的特征向量，则称G是调和图，其中d（vi）表示顶点弘的度．1—4圈的调和图已经确定，本文确定了所有的3-调和的5-圈调和图．     

路和圈多重联图的邻点可区别E-全染色

设G（V,E）是一个简单图,k是一个正整数,f是一个V（G）∪E（G）到{1,2,...,k}的映射.如果u,v∈E（G）,则f（u）=f（v）,f（u）=f（uv）,f（v）=f（uv）,C（u）=C（v）,其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.讨论了路和圈的多重联图的邻点可区别E-全色数。