一类裂变图的L(0,1,2 d,d,1)-标号数上界

将图的标号问题由每个顶点需要一个标号的情况推广到每个顶点需要多个标号的情况,给出裂变图的概念以及赋权图的L(0,1,2 d,d,1)-标号的概念,给出R-单位球图对应裂变图的L(0,1,2 d,d,1)-标号数的一个上界.     

一类裂变图的$L(^{0,1,2}_{d,d,1})$-标号数上界

将图的标号问题由每个琢真需要一个标号的情况推广到每个顶点需要多个标号的情况，给出裂变图的概念以及赋权图的L（0,1,2↑ d,d,1）-标号的概念，给出R．单位球图对应裂变图的L（0,1,2↑ d,d,1）-标号数的一个上界．     

竖梯的局部替换图的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(d1,d2)-标号问题

图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(d1,d2)-标号,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d1,d2)-标号的上界,作为推论,本文证明了对上述几类图,有上述猜想成立.     

关于可嵌人曲面图的列表(d,1)-全标号问题

图的(d,1)-全标号问题最初是由Havet等人提出的.在本文中,我们考虑了可嵌入曲面图的列表(d,1)-全标号问题,并证明了其列表(d,1)-全标号数不超过△(G)+2d.     

关于图的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(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)-标号数.     

点接手镯图的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)-标号数的确切值.     

两类图的(d,1)-全标号

主要讨论了W_n与C_m的笛卡尔积和均衡完全r-部图K_r(n)的(d,1)-全标号,并得出了(d,1)-全数λ_d~T(W_n□C_m)和λ_d~T(K_(r(n)))的确切值.     

关于图的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)的上界 .     

关于几类图的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图的λ值的上界 ,并证明了上述猜想对以上几类图成立     

弦图的L(3,2,1)}-标号

图 G 的一个 L(3,2,1)- 标号是指从 V(G) 到非负整数集的一个映射 f, 满足: 当 d_G(u,v)=1 时, |f(u)-f(v)|\geq 3; 当 d_G(u,v)=2 时, |f(u)-f(v)|\geq 2; 当 d_G(u,v)=1 时, |f(u)-f(v)|\geq 1. L(3,2,1)-标号问题就是确定出最小的整数 \lambda_3(G) 使得 G存在最大标号不超过该数的 L(3,2,1)- 标号. 本文研究了弦图的 L(3,2,1)- 标号问题,获得了弦图及其一些子类, 如扇, r- 路,r- 树等的 \lambda_3 数的界.     

E~(G(i))类图簇的伴随多项式的因式分解及色性分析

设Sn+1是n+1个顶点的星图,G是任意的p阶连通图.ΨG(i)(n,p)表示把Sn+1的n度点与G的第i(1 i p)个顶点重迭后得到的图;ErG(p+i)(r-1)表示把rG的r-1个分支的第i个顶点依次与Sr的r-1个1度点邻接,同时把剩下的一个图G的第i个顶点与Sr的r-1度点重迭后得到的图.我们通过讨论图簇ErG(p+i)(r-1)∪(r-1)K1的伴随多项式的因式分解,证明了它的补图的色等价图的结构性质.     

图簇Y_(λ_kδ)∪β_kS_δ~*的伴随分解及其补图的色等价性

设P_n是具有n个顶点的路,令δ=rn+1,我们S_δ~*表示把rP_(n+1)的每个分支的一个1度点重迭在一起得到的图.用Y_(λ_1δ)~(S*)表示把r_1S_δ~*中每个分支的r度顶点与S_δ~*的r度顶点依次邻接后得到的图,Y_(λ_2δ)~(S*)表示把用r_2Y_(λ_1δ)~(S*)中每个分支的r+r1度顶点与S_δ~*的r度顶点依次邻接后得到的图,一般地,Y_(λ_kδ)~(S*)表示把用r_kY_(λ_(k-1)δ)~(S*)中每个分支的r+r_k-1度顶点与S_δ~*的r度顶点依次邻接后得到的图,运用图的伴随多项式的性质,证明了图Y_(λ_kδ)~(S*)∪β_kS_δ~*的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价性.     

关于图的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)的上界 .     

L(d1, d2,..., dt)-Number λ(Cn; d1, d2,...,dt) of Cycles

An L(d1,d2,...,dt)-labeling of a graph G is a function f from its vertex set V(G) to the set {0, 1,..., k} for some positive integer k such that {f(x) - f(y)| ≥ di, if the distance between vertices x and y in G is equal to i for i = 1,2,...,t. The L(d1,d2,...,dt)-number λ(G;d1,d2,... ,dt) of G is the smallest integer number k such that G has an L(d1,d2,... ,dt)labeling with max{f(x)|x ∈ V(G)} = k. In this paper, we obtain the exact values for λ(Cn; 2, 2,1) and λ(Cn; 3, 2, 1), and present lower and upper bounds for λ(Cn; 2,..., 2,1,..., 1)     

单圈共轭图的最小广义Randic指标R-1

图G的广义Randic指标定义为Rα=Rα（G）=∑uv∈E（G）（d（u）d（v））^α,其中d（u）是G的顶点u的度,α是任意实数．本文确定了单圈共轭图的广义Randic指标R-1的严格下界,并刻划了达到最小R-1的极图,这类极图还是化学图．