图的（p，1）-全标号及图的弱邻点可区分的染色问题
|
摘要
图理论是一门非常年轻的学科,在许多的科学领域都有着广泛的应用背景.图的染色问题是图理论的一个重要组成部分,而且许多经典的染色问题诸如点染色和边染色等都已经有了深入的研究.随着科技的进步,在各种新的科技问题的背景之下,许多新的染色问题也被相继提出.
在无线电网络中分配传播的波段的问题时,产生了一个频道分配问题.如果几个站点是相邻的,为了避免发射的信号相互干扰,那么在给这些相邻的站点分配频道时,它们得到的频道相差至少为2；而且如果两个站点离得近(但不是非常近),那么分配给它们的频道也需要不同.如果把这个问题转化成图论的染色问题就是Griggs和Yeh提出的L(2,1)-标号问题[4].2000年,G.J.Chang等人把它推广到图的L(p,1)-标号[5].
图G的L(p,1)-标号是对G的顶点集的一个整数映射L,使得对任意的顶点u,υ满足：
(1)若dG(u,v)=1,则|L(u)-L(v)|≥p；
(2)若dG(u,v)=2,则|L(u)-L(v)|≥1,(其中dG(u,v)表示u,v两点之间的距离).
一个图G的关联图[6]是指把图G的每一条边用长为2的路代替.图G的关联图的L(p,1)-标号,是对G的一个特别的全染色,这种全染色就是由Havet和Yu提出的(p,1)-全标号[7].
设p是一个正整数,图G的一个k-(p,1)-全标号是一个映射f：V(G)∪E(G)→{0,1,…,κ｝,使得：
(1)G的任意两个相邻的顶点u,v,有|f(u)-f(v)|≥1；
(2)G的任意两条相邻的边e,e',有|f(e)-f(e')|≥1；
(3)G的任意两个关联的点u和边e,有|f(u)-f(e)|≥p.我们称这样的一个标号叫G的(p,1)-全标号.(p,1)-全标号的跨度是指标号中的最大标号与最小标号的差.G的(p,1)-全标号的最小跨度叫(p,1)-全标号数,记作λPT(G),即λPT(G)=min｛k|G有一个k-(p,1)-全标号｝.
图的邻点可区分的边染色(邻强边染色)[8]和邻点可区分的全染色[9]是由张忠辅老师首先提出的,在数据传输问题上有一定的应用背景,但是由于限制的条件比较强目前仅在树,圈,完全图等图类上得到了解决.
Hajo Broersma[10]曾经把古典的顶点标号进行变形,把对原图G的限制放松到主干道上,提出了一种新的染色一主干道染色(Back Bone coloring).我们沿用此思想在本文中将邻点可区分的全(边)染色的条件限制在支撑树上,提出了如下两种定义：
定义1给定一个简单连通图G,k为一个正整数,f是G的一个正常边染色,f：E(G)→{1,2,…k｝,设、T是G的一棵支撑树,记C(u)={f(uw)|w∈N(u)},如果对任意的uv∈E(T)满足C(u)≠C(v),则f称为G的T-邻强边染色.记XTas(G,T)=min{k|G有一个k-T-邻强边染色｝,
定义2给定一个简单连通图G,k为一个正整数,f是G的一个正常全染色,f：V(G)∪E(G)→{1,2,…k｝,设T是G的一棵支撑树,记C(u)={f(u)∪f(uw)|w∈N(u)｝,如果对任意的uv∈E(T),满足C(u)≠C(v),则f称为G的T-邻点可区分的全染色.记XTat(G,T)=min{k|G有一个k-T-邻点可区分的全染色}.
显然这两个定义的条件要比张忠辅老师提出的邻点可区分的全(边)染色的定义要弱一些,所以我们称这两种新的染色问题为图的弱邻点可区分的染色问题.
在本文的第一章里,我们主要介绍了文章中所涉及的一些概念、术语和符号以及图染色问题的发展情况.在第二章中,我们研究了图的(p,1)-全标号,给出了当p=3,Δ≥9时,全标号的一个上界和特殊图的(p,1)-全标号.第三章中研究了T-邻点可区分的全(边)染色,并给出了这两种染色在任意图上的一个上界,以及在一些具体图类上的上界.
定理2.1.5设任意图G,Δ(G)≥9,则λ3T(G)≤2Δ(G)+1.
定理2.2.4非正则二部图G,Δ(G)=Δ,且图G的最大度点导出子图包含K1,Δ-1,则λpT(G)=Δ+p,(p≥22).
定理3.1.2若图G是连通图,Δ(G)=Δ,则对G的任意支撑树T,χ'Tas(G,T)≤2Δ+1.
定理3.1.4若图G是简单连通图,Δ(G)=Δ,T是G的任意一棵支撑树,则χTat(G,T)≤3Δ+2.
定义3.2.1若简单图G=(V(G),E(G)),V(G)={v1,v2,…,vn｝,图G'的点集和边集定义如下：
V(G')={v1,v2,…,vn,v1',v2',…,vn'｝,E(G')＝{vivj,vi'vj,vivj',vi'vj'|vivj∈E(G)｝,则图G'称为图G的点分裂图.
根据点分裂图的定义可知,原图和点分裂图满足：Δ(G')=2Δ(G),δ(G')=2δ(G)且对任意的v∈V(G'),dG'(v)=2dG(v).
定理3.2.1图G'为连通图G的分裂图,则G'存在一棵支撑树T',使得χ'Tas(G',T')≤3/2Δ(G')+1.
定理3.2.2若图G/为连通图G的分裂图,则G'存在一棵支撑树T',使得χTat(G',T')≤5/2Δ(G')+2.
定义3.3.1设G1,G2为简单图,若|G1|=n1,V(G1)={u1,u2,…,un1}|G2|=n2,V(G2)={υ1,u2,…,un2｝,G1×G2的点集和边集定义如下：
V(G1×G2)={uivj|i=1,2,…,n1,J=1,2,…,n2｝；
E(G1×G2)={(uivj)(ukvl)|vj=vl且(ｕiｕk)∈E(G1)或ui=uk且(vjvl)∈E(G2),i,k=1,2,…,n1；J,ι=1,2,…,n2｝.
则G1×G2为G1,G2的笛卡尔乘积图.
定理3.3.1若连通图G1,最大度为Δ(G1),连通图G2,最大度为Δ(G2),Δ(G1)≤Δ(G2),则其笛卡尔乘积图G1×G2,存在支撑树T,使得χ'Tas(G1×G2,T)≤2Δ(G1)+Δ(G2)+1.
定理3.3.2若连通图G1,最大度为Δ(G1),连通图G2,最大度为Δ(G2),Δ(G1)≤Δ(G2),则其笛卡尔乘积图G1×G2,存在支撑树T,使得χTat(G1×G2,T)≤3Δ(G1)+2Δ(G2)+2.
另外我们还研究了一些特殊图类的T-邻点可区分的全染色和边染色.
The graph theory which has extensive application in many science fields is a young subject.And the coloring problem of graphs is one of the important parts in the graph theory. Many classic coloring problems such as vertex coloring and edge coloring have been deeply studied. With the development of technology,a lot of new coloring prob-lems are proposed continuously under the background of technology.
The channel assignment problem was produced in the assignment problem of the radio network.In order to avoid interference, if two stations are too close, the separation of the channels assigned to them has to be at least two; if.two stations are close (but not too close), they must receive different channels.If this problem was inverted to problem of graph of theory,it was the L(2,1)-labeling problem which was produced by Griggs and Yeh[4].In 2000,G.J.Cahang[5] etc.generalized this problem to the L(p,1)-labeling.
The L(p,1)-labeling of a graph G is an integer assignment L to the vertex set V(G) such that:
|L(u)-L(v)|≥p if dG(u,v)=1;
|L(u)-L(v)|≥1 if dG(u,v)=2;
The incidence graph[6] of G is the graph obtained by replacing each edge of G with a path of length 2. the L(p, 1)-labeling of the incidence graphs of G is a special total coloring of G.This kind of total coloring is (p,1)-total labeling introduced by Havet and Yu[7].
Let p be an positive integer,a k-(p,1)-total labeling of a graph G is a mapping
f:V(G)∪E(G)→{0,1,…,k},such that:
(1)for any two adjacent vertices u,vof G,having |f(u)-,f(v)|≥1；
(2)for any two adjacent edges e,e'of G,having |f(e)-f(e')|≥1；
(3)for a vertex u and its incident edge e of G,having |f(u)-f(e)|≥p.
We call such an assignment a(p,1)-total labeling of G.The span of a(p,1)-total labeling is the difference between the maximum label and the minimal label. The (p,1)-total number of a graph G,is the minimum span of (p,1)-total labeling of G,denoted byλpT(G),andλpT(G)=min{k|G has a k-(p,1)-total labeling}.
The adjacent vertex distinguishing edge coloring(adjacent strong edge coloring)[9] and the adjacent vertex distinguishing total coloring[10]which had a application in data transmission were first introduced by Zhang Zhongfu, As the restriction was so strong that the problem was resolved only on some graphs such as tree,circle and complete graphs etc.Hajo Broersma[11] has varied the classic vertex coloring and put the restric-tions only on the backbone of G.This new kind coloring was called BackBone coloring. We use this cogitation and put the conditions of the adjacent vertex distinguishing edge coloring and the adjacent vertex distinguishing total coloing on the spanning tree of G.So we propose the following two definitions:
Definition 1 G is a given simple connected graph,let k be a positive integer,and f is a proper edge coloring of G,f:E(G)→{1,2,…k},let T be a spanning tree of G,C(u)={f(uw)|w∈N(u)},if any edge uv∈E(T) satisfies C(u)≠C(v),then f is called a T-adjacent vertex distinguishing edge coloring of G.χTas(G,T)=min{k|G has a k-T-adjacent vertex distinguishing edge coloring}.
Definition 2 G is a given simple connected graph,let k be a positive integer,and f is a proper total coloring of G,f:V(G)∪E(G)→{1,2,…k},let T be a spanning tree of G,C(u)={f(u)∪f(uw)|w∈N(u)},if any edge uv∈E(T)satisfies C(u)≠C(v),then f is called a T-adjacent vertex distinguishing total coloring of G.χTat(G,T)=min{k|G has a k-T-adjacent vertex distinguishing total coloring}.
Obviously the restrictions in the two definitions are weaken than that in adjacent vertex distinguishing total(edge) coloring which were proposed by Zhang Zhongfu,so this kind of new coloring problem was called weak adjacent vertex distinguishing coloring problem.
In the first chapter of this pap er,we mainly introduced some concepts,terminologies,sy-mbols and the development of theory coloring problem.In the second chapter,we studied the(p,1)一total labeling,and gave a(P,1)-total labeling bound when p=3,△≥9,and also gave bounds on some special graphs.In the third chapter,we studied T—adjacent vertex distinguishing total(edge) colring and we gave this two kinds of coloring two bounds on any a graph and some special graphs.
We briefly summerize our main results as follows:
Theorem 2.1.5 Let G be any a graph with△(G)≥9,thenλ3T(G)≤2△(G)+1.
Theorem 2.2.4 Non-regular Bipartite graph G,△(G)=△,and the induced sub-graph of maximal degree vertex of G contains K1,△-1,thenλPT(G)=△+p,(P≥2).
Theorem 3.1.2 If G is a connected graph,△(G)=△,and T is any a spanning tree of G,then x'Tas(G,T)≤2△+1.
.Theorem 3.1.4 If G is a connected graph,△(G)=△,and T is any a spanning tree of G,then xTat(G,T)≤3△+2.
Definition 3.2.1[11] If a simple G=(V(G),E(G)),V(G)={v1,v2,…,vn},the vertex set and edge set of G' is definited as follows:
V(G')={v1,v2,…,vn,v1',v'2,…,v'n},E(G')={vivj,v'ivj,viv'j,v'iv'j|vivj∈E(G)},then G' is called the vertex split graph of G.
According to the definition of the vertex split graph,we know that the graph G and the vertex split graph satisfy the following relationship:△(G')=2△(G),δ(G')=2δ(G) and u∈V(G'),dG'(u)=2dG(u).
Theorem 3.2.1 G'is the vertex split graph of G,then G'exists a spanning tree T',such that xTas(G',T')≤3/2△(G')+1.
Theorem 3.2.2 If G'is the vertex split graph of G,then G' exists a spanning tree T',such that xTat(G',T')≤5/2△(G')+2.
Definition 3.3.1[12,13] Let G1,G2 be the simple graphs,if |G1|=n1,V(G1)= {u1,u2,…,un1)；|G2|=n2,V(G2)={v1,v2,…,Vn2),we define the vertex set and edge set of G1×G2 as follows:
V(G1×G2)={uivj|i=1,2,…,n1,j=1,2,…,n2}；
E(G1×G2)={(uivj)(ukvl)|uj=vl and(uiuk)∈E(G1) or ui=uk and(vjvl)∈E(G2),i,k=1,2,…,n1,j,l=1,2,…,n2}.
Then G1×G2 is called the cartesian product graph of G1,G2.
Theorem 3.3.1 GI is a connected graph with maimum degree△(G1),G2 is a connected graph with maximum degree△(G2),△(G1)≤△(G2),then the carte-sian product graph G1×G2 exists a spanning tree T,such thatxTas(G1×G2,T)≤2△(G1)+△(G2)+1.
Theorem 3.3.2 G1 is a connected graph with maximum degree△(G1), G2 is a connected graph with maximum degree△(G2),△(G1)≤△(G2),then the carte-sian product graph G1×G2 exists a spanning tree T,such that xTat(G1×G2,T)≤3△(G1)+2△(G2)+2.
In addtion,w.e studied the T-adjacent vertex distinguishing tot al(edge)coloring of special graphs.
在无线电网络中分配传播的波段的问题时,产生了一个频道分配问题.如果几个站点是相邻的,为了避免发射的信号相互干扰,那么在给这些相邻的站点分配频道时,它们得到的频道相差至少为2；而且如果两个站点离得近(但不是非常近),那么分配给它们的频道也需要不同.如果把这个问题转化成图论的染色问题就是Griggs和Yeh提出的L(2,1)-标号问题[4].2000年,G.J.Chang等人把它推广到图的L(p,1)-标号[5].
图G的L(p,1)-标号是对G的顶点集的一个整数映射L,使得对任意的顶点u,υ满足：
(1)若dG(u,v)=1,则|L(u)-L(v)|≥p；
(2)若dG(u,v)=2,则|L(u)-L(v)|≥1,(其中dG(u,v)表示u,v两点之间的距离).
一个图G的关联图[6]是指把图G的每一条边用长为2的路代替.图G的关联图的L(p,1)-标号,是对G的一个特别的全染色,这种全染色就是由Havet和Yu提出的(p,1)-全标号[7].
设p是一个正整数,图G的一个k-(p,1)-全标号是一个映射f：V(G)∪E(G)→{0,1,…,κ｝,使得：
(1)G的任意两个相邻的顶点u,v,有|f(u)-f(v)|≥1；
(2)G的任意两条相邻的边e,e',有|f(e)-f(e')|≥1；
(3)G的任意两个关联的点u和边e,有|f(u)-f(e)|≥p.我们称这样的一个标号叫G的(p,1)-全标号.(p,1)-全标号的跨度是指标号中的最大标号与最小标号的差.G的(p,1)-全标号的最小跨度叫(p,1)-全标号数,记作λPT(G),即λPT(G)=min｛k|G有一个k-(p,1)-全标号｝.
图的邻点可区分的边染色(邻强边染色)[8]和邻点可区分的全染色[9]是由张忠辅老师首先提出的,在数据传输问题上有一定的应用背景,但是由于限制的条件比较强目前仅在树,圈,完全图等图类上得到了解决.
Hajo Broersma[10]曾经把古典的顶点标号进行变形,把对原图G的限制放松到主干道上,提出了一种新的染色一主干道染色(Back Bone coloring).我们沿用此思想在本文中将邻点可区分的全(边)染色的条件限制在支撑树上,提出了如下两种定义：
定义1给定一个简单连通图G,k为一个正整数,f是G的一个正常边染色,f：E(G)→{1,2,…k｝,设、T是G的一棵支撑树,记C(u)={f(uw)|w∈N(u)},如果对任意的uv∈E(T)满足C(u)≠C(v),则f称为G的T-邻强边染色.记XTas(G,T)=min{k|G有一个k-T-邻强边染色｝,
定义2给定一个简单连通图G,k为一个正整数,f是G的一个正常全染色,f：V(G)∪E(G)→{1,2,…k｝,设T是G的一棵支撑树,记C(u)={f(u)∪f(uw)|w∈N(u)｝,如果对任意的uv∈E(T),满足C(u)≠C(v),则f称为G的T-邻点可区分的全染色.记XTat(G,T)=min{k|G有一个k-T-邻点可区分的全染色}.
显然这两个定义的条件要比张忠辅老师提出的邻点可区分的全(边)染色的定义要弱一些,所以我们称这两种新的染色问题为图的弱邻点可区分的染色问题.
在本文的第一章里,我们主要介绍了文章中所涉及的一些概念、术语和符号以及图染色问题的发展情况.在第二章中,我们研究了图的(p,1)-全标号,给出了当p=3,Δ≥9时,全标号的一个上界和特殊图的(p,1)-全标号.第三章中研究了T-邻点可区分的全(边)染色,并给出了这两种染色在任意图上的一个上界,以及在一些具体图类上的上界.
定理2.1.5设任意图G,Δ(G)≥9,则λ3T(G)≤2Δ(G)+1.
定理2.2.4非正则二部图G,Δ(G)=Δ,且图G的最大度点导出子图包含K1,Δ-1,则λpT(G)=Δ+p,(p≥22).
定理3.1.2若图G是连通图,Δ(G)=Δ,则对G的任意支撑树T,χ'Tas(G,T)≤2Δ+1.
定理3.1.4若图G是简单连通图,Δ(G)=Δ,T是G的任意一棵支撑树,则χTat(G,T)≤3Δ+2.
定义3.2.1若简单图G=(V(G),E(G)),V(G)={v1,v2,…,vn｝,图G'的点集和边集定义如下：
V(G')={v1,v2,…,vn,v1',v2',…,vn'｝,E(G')＝{vivj,vi'vj,vivj',vi'vj'|vivj∈E(G)｝,则图G'称为图G的点分裂图.
根据点分裂图的定义可知,原图和点分裂图满足：Δ(G')=2Δ(G),δ(G')=2δ(G)且对任意的v∈V(G'),dG'(v)=2dG(v).
定理3.2.1图G'为连通图G的分裂图,则G'存在一棵支撑树T',使得χ'Tas(G',T')≤3/2Δ(G')+1.
定理3.2.2若图G/为连通图G的分裂图,则G'存在一棵支撑树T',使得χTat(G',T')≤5/2Δ(G')+2.
定义3.3.1设G1,G2为简单图,若|G1|=n1,V(G1)={u1,u2,…,un1}|G2|=n2,V(G2)={υ1,u2,…,un2｝,G1×G2的点集和边集定义如下：
V(G1×G2)={uivj|i=1,2,…,n1,J=1,2,…,n2｝；
E(G1×G2)={(uivj)(ukvl)|vj=vl且(ｕiｕk)∈E(G1)或ui=uk且(vjvl)∈E(G2),i,k=1,2,…,n1；J,ι=1,2,…,n2｝.
则G1×G2为G1,G2的笛卡尔乘积图.
定理3.3.1若连通图G1,最大度为Δ(G1),连通图G2,最大度为Δ(G2),Δ(G1)≤Δ(G2),则其笛卡尔乘积图G1×G2,存在支撑树T,使得χ'Tas(G1×G2,T)≤2Δ(G1)+Δ(G2)+1.
定理3.3.2若连通图G1,最大度为Δ(G1),连通图G2,最大度为Δ(G2),Δ(G1)≤Δ(G2),则其笛卡尔乘积图G1×G2,存在支撑树T,使得χTat(G1×G2,T)≤3Δ(G1)+2Δ(G2)+2.
另外我们还研究了一些特殊图类的T-邻点可区分的全染色和边染色.
The graph theory which has extensive application in many science fields is a young subject.And the coloring problem of graphs is one of the important parts in the graph theory. Many classic coloring problems such as vertex coloring and edge coloring have been deeply studied. With the development of technology,a lot of new coloring prob-lems are proposed continuously under the background of technology.
The channel assignment problem was produced in the assignment problem of the radio network.In order to avoid interference, if two stations are too close, the separation of the channels assigned to them has to be at least two; if.two stations are close (but not too close), they must receive different channels.If this problem was inverted to problem of graph of theory,it was the L(2,1)-labeling problem which was produced by Griggs and Yeh[4].In 2000,G.J.Cahang[5] etc.generalized this problem to the L(p,1)-labeling.
The L(p,1)-labeling of a graph G is an integer assignment L to the vertex set V(G) such that:
|L(u)-L(v)|≥p if dG(u,v)=1;
|L(u)-L(v)|≥1 if dG(u,v)=2;
The incidence graph[6] of G is the graph obtained by replacing each edge of G with a path of length 2. the L(p, 1)-labeling of the incidence graphs of G is a special total coloring of G.This kind of total coloring is (p,1)-total labeling introduced by Havet and Yu[7].
Let p be an positive integer,a k-(p,1)-total labeling of a graph G is a mapping
f:V(G)∪E(G)→{0,1,…,k},such that:
(1)for any two adjacent vertices u,vof G,having |f(u)-,f(v)|≥1；
(2)for any two adjacent edges e,e'of G,having |f(e)-f(e')|≥1；
(3)for a vertex u and its incident edge e of G,having |f(u)-f(e)|≥p.
We call such an assignment a(p,1)-total labeling of G.The span of a(p,1)-total labeling is the difference between the maximum label and the minimal label. The (p,1)-total number of a graph G,is the minimum span of (p,1)-total labeling of G,denoted byλpT(G),andλpT(G)=min{k|G has a k-(p,1)-total labeling}.
The adjacent vertex distinguishing edge coloring(adjacent strong edge coloring)[9] and the adjacent vertex distinguishing total coloring[10]which had a application in data transmission were first introduced by Zhang Zhongfu, As the restriction was so strong that the problem was resolved only on some graphs such as tree,circle and complete graphs etc.Hajo Broersma[11] has varied the classic vertex coloring and put the restric-tions only on the backbone of G.This new kind coloring was called BackBone coloring. We use this cogitation and put the conditions of the adjacent vertex distinguishing edge coloring and the adjacent vertex distinguishing total coloing on the spanning tree of G.So we propose the following two definitions:
Definition 1 G is a given simple connected graph,let k be a positive integer,and f is a proper edge coloring of G,f:E(G)→{1,2,…k},let T be a spanning tree of G,C(u)={f(uw)|w∈N(u)},if any edge uv∈E(T) satisfies C(u)≠C(v),then f is called a T-adjacent vertex distinguishing edge coloring of G.χTas(G,T)=min{k|G has a k-T-adjacent vertex distinguishing edge coloring}.
Definition 2 G is a given simple connected graph,let k be a positive integer,and f is a proper total coloring of G,f:V(G)∪E(G)→{1,2,…k},let T be a spanning tree of G,C(u)={f(u)∪f(uw)|w∈N(u)},if any edge uv∈E(T)satisfies C(u)≠C(v),then f is called a T-adjacent vertex distinguishing total coloring of G.χTat(G,T)=min{k|G has a k-T-adjacent vertex distinguishing total coloring}.
Obviously the restrictions in the two definitions are weaken than that in adjacent vertex distinguishing total(edge) coloring which were proposed by Zhang Zhongfu,so this kind of new coloring problem was called weak adjacent vertex distinguishing coloring problem.
In the first chapter of this pap er,we mainly introduced some concepts,terminologies,sy-mbols and the development of theory coloring problem.In the second chapter,we studied the(p,1)一total labeling,and gave a(P,1)-total labeling bound when p=3,△≥9,and also gave bounds on some special graphs.In the third chapter,we studied T—adjacent vertex distinguishing total(edge) colring and we gave this two kinds of coloring two bounds on any a graph and some special graphs.
We briefly summerize our main results as follows:
Theorem 2.1.5 Let G be any a graph with△(G)≥9,thenλ3T(G)≤2△(G)+1.
Theorem 2.2.4 Non-regular Bipartite graph G,△(G)=△,and the induced sub-graph of maximal degree vertex of G contains K1,△-1,thenλPT(G)=△+p,(P≥2).
Theorem 3.1.2 If G is a connected graph,△(G)=△,and T is any a spanning tree of G,then x'Tas(G,T)≤2△+1.
.Theorem 3.1.4 If G is a connected graph,△(G)=△,and T is any a spanning tree of G,then xTat(G,T)≤3△+2.
Definition 3.2.1[11] If a simple G=(V(G),E(G)),V(G)={v1,v2,…,vn},the vertex set and edge set of G' is definited as follows:
V(G')={v1,v2,…,vn,v1',v'2,…,v'n},E(G')={vivj,v'ivj,viv'j,v'iv'j|vivj∈E(G)},then G' is called the vertex split graph of G.
According to the definition of the vertex split graph,we know that the graph G and the vertex split graph satisfy the following relationship:△(G')=2△(G),δ(G')=2δ(G) and u∈V(G'),dG'(u)=2dG(u).
Theorem 3.2.1 G'is the vertex split graph of G,then G'exists a spanning tree T',such that xTas(G',T')≤3/2△(G')+1.
Theorem 3.2.2 If G'is the vertex split graph of G,then G' exists a spanning tree T',such that xTat(G',T')≤5/2△(G')+2.
Definition 3.3.1[12,13] Let G1,G2 be the simple graphs,if |G1|=n1,V(G1)= {u1,u2,…,un1)；|G2|=n2,V(G2)={v1,v2,…,Vn2),we define the vertex set and edge set of G1×G2 as follows:
V(G1×G2)={uivj|i=1,2,…,n1,j=1,2,…,n2}；
E(G1×G2)={(uivj)(ukvl)|uj=vl and(uiuk)∈E(G1) or ui=uk and(vjvl)∈E(G2),i,k=1,2,…,n1,j,l=1,2,…,n2}.
Then G1×G2 is called the cartesian product graph of G1,G2.
Theorem 3.3.1 GI is a connected graph with maimum degree△(G1),G2 is a connected graph with maximum degree△(G2),△(G1)≤△(G2),then the carte-sian product graph G1×G2 exists a spanning tree T,such thatxTas(G1×G2,T)≤2△(G1)+△(G2)+1.
Theorem 3.3.2 G1 is a connected graph with maximum degree△(G1), G2 is a connected graph with maximum degree△(G2),△(G1)≤△(G2),then the carte-sian product graph G1×G2 exists a spanning tree T,such that xTat(G1×G2,T)≤3△(G1)+2△(G2)+2.
In addtion,w.e studied the T-adjacent vertex distinguishing tot al(edge)coloring of special graphs.
引文
[1]K.appel and W.Haken.Every planar map is four colorable Part Ⅰ:Discharging[J].Illinois J.Math,1977,21:429-490.
[2]K.appel and W.Haken.and J.Koch.Every planar map is four colorable Part Ⅱ:Re-ducibility [J]. Illinois J.Math,1977,21:491-567.
[3]Vizing V.G..On an estimate of the chromatic class of a p-graph(in Russian) [J].Metody Diskret,Anali:1964,3:25-30.
[4]J.R. Griggs,R.K. Yeh.Labelling graphs with a condition at distance two[J].SIAM J.Discrete Math,1992,5:586-595.
[5]G.J.Chang,W.-T.Ke.D.Kuo,D.D.-F.Liu,R.K.Yeh.On L(d,1)-lanelling of graphs[J]. Discrete Math,2000,220:57-66.
[6]M.A. Whittlesey,J.P. Georges,D.W. Mauro.On the λ-number of Qn and related graphs [J]. SIAM J.Discrete Math,1995,8:449-506.
[7]F.Havet,M.-L.Yu,(d,1)-Total Labeling of graphs, Technical Report 4650,INRIA,2002.
[8]Zhang Zhongfu,Li Jingwen,Chen Xiang'en,etc.,D(β) Vertext Distinguishiing Proper Edge Coloring of Graphs, Acta Mathematics Sinica Vol.49,No.2,703-708.
[9]Zhang Zhongfu,Chen xiang'en,Li Jingwen,etc.,On The Adjacent Vertext Distin-guishiing Total Coloring of Graphs,Science in china.Vol.34,No.5(2004),574-583.
[10]Hajo,Fedor V.Fomin,etc.,Backbone Colorings for Graphs:Tree and Path Backbone[J],Journal of Graph Theory,2007,137-151.
[11]T.Jensen and B.Toft.Graph Coloring Problems[M]. Wiley,1995:261-262.
[12]Sandi Klavzar.Coloring graph Products-A survey[J].Discrete Math,1996,155:135-145.
[13]T.Jensen and B.Toft.Graph Coloring Problems[M]. Wiley,1995:261-262.
[14]J.A.Bondy, U.S.R.Murty.Graph Theroy with Application[M].London:MacMillan Press,1976.
[15]Bollobas B. Modern Graphy Theory[M]. New York:Springer-Verlag,1998.
[16]J.Beck,An Algorithmic Approach to the Lovasz Local Lemma,Random Structures and Algorithms 2(1991),343-365.
[17]F.Havet,M.-L. Yu.(p,1)-Total labelling of graphs [J].Discrete. Math,2008,308:496-513.
[18]F.Havet,S. Thomasse. Complexity of (p,1)-total labelling.manuscript,2006.
[19]A.C.Burris.Vertext Distinguishing Edge Coloring,PhD.Disiertation,Memphis State University.August 1993.
[20]张珊珊. 图的(ρ,1)-全标号.[D],济南.山东师范大学,2009.
[21]陈丽华. 图的(ρ,1)-全标号.[D],济南.山东师范大学,2009.
[22]Zhang Zhongfu,Liu Linzhong,Wang Jianfang. Adiacent Strong Edge Coloing of Graphs. Applied Mathematics Letters 15 (2002)623-626.
[23]Zhang Zhongfu,Chen xiang'en,Li Jingwen,Yao Bing,Lu Xingzhong,Wang Jianfan.Science in China Ser.A Mathematics 2005 Vol.48 No.3 289-299.
[2]K.appel and W.Haken.and J.Koch.Every planar map is four colorable Part Ⅱ:Re-ducibility [J]. Illinois J.Math,1977,21:491-567.
[3]Vizing V.G..On an estimate of the chromatic class of a p-graph(in Russian) [J].Metody Diskret,Anali:1964,3:25-30.
[4]J.R. Griggs,R.K. Yeh.Labelling graphs with a condition at distance two[J].SIAM J.Discrete Math,1992,5:586-595.
[5]G.J.Chang,W.-T.Ke.D.Kuo,D.D.-F.Liu,R.K.Yeh.On L(d,1)-lanelling of graphs[J]. Discrete Math,2000,220:57-66.
[6]M.A. Whittlesey,J.P. Georges,D.W. Mauro.On the λ-number of Qn and related graphs [J]. SIAM J.Discrete Math,1995,8:449-506.
[7]F.Havet,M.-L.Yu,(d,1)-Total Labeling of graphs, Technical Report 4650,INRIA,2002.
[8]Zhang Zhongfu,Li Jingwen,Chen Xiang'en,etc.,D(β) Vertext Distinguishiing Proper Edge Coloring of Graphs, Acta Mathematics Sinica Vol.49,No.2,703-708.
[9]Zhang Zhongfu,Chen xiang'en,Li Jingwen,etc.,On The Adjacent Vertext Distin-guishiing Total Coloring of Graphs,Science in china.Vol.34,No.5(2004),574-583.
[10]Hajo,Fedor V.Fomin,etc.,Backbone Colorings for Graphs:Tree and Path Backbone[J],Journal of Graph Theory,2007,137-151.
[11]T.Jensen and B.Toft.Graph Coloring Problems[M]. Wiley,1995:261-262.
[12]Sandi Klavzar.Coloring graph Products-A survey[J].Discrete Math,1996,155:135-145.
[13]T.Jensen and B.Toft.Graph Coloring Problems[M]. Wiley,1995:261-262.
[14]J.A.Bondy, U.S.R.Murty.Graph Theroy with Application[M].London:MacMillan Press,1976.
[15]Bollobas B. Modern Graphy Theory[M]. New York:Springer-Verlag,1998.
[16]J.Beck,An Algorithmic Approach to the Lovasz Local Lemma,Random Structures and Algorithms 2(1991),343-365.
[17]F.Havet,M.-L. Yu.(p,1)-Total labelling of graphs [J].Discrete. Math,2008,308:496-513.
[18]F.Havet,S. Thomasse. Complexity of (p,1)-total labelling.manuscript,2006.
[19]A.C.Burris.Vertext Distinguishing Edge Coloring,PhD.Disiertation,Memphis State University.August 1993.
[20]张珊珊. 图的(ρ,1)-全标号.[D],济南.山东师范大学,2009.
[21]陈丽华. 图的(ρ,1)-全标号.[D],济南.山东师范大学,2009.
[22]Zhang Zhongfu,Liu Linzhong,Wang Jianfang. Adiacent Strong Edge Coloing of Graphs. Applied Mathematics Letters 15 (2002)623-626.
[23]Zhang Zhongfu,Chen xiang'en,Li Jingwen,Yao Bing,Lu Xingzhong,Wang Jianfan.Science in China Ser.A Mathematics 2005 Vol.48 No.3 289-299.