(d,1)-total Labeling And Two L(d,1)-labelings Restricted On The Spanning Tree

Graph theory is a young but rapidly maturing subject. It can be applied in various science fields such as:computer science, cryptography, physics, biology, chemistry, strate-gy etc.Graph theory and algorithm were used in all of them widely.Graph coloring problem is one of the important problems and an active research field in graph theory.Graph labeling is a kind of graph coloring problems.As a variation of the channel assignment problem,Griggs and Yeh introduced the L(2,1)-labeling.Given some transmitters and we want to assign channels on them.In or-der to avoid interference,if two transmitters are too close,then the separation of the chan-nels assigned to them has to be at least two.Moreover,if two transmitters are close(but not too close),then they must receive different channels.In 2000,G.J.Cahang etc.generalized this problem to the L(d,1)-labeling.We only consider the simple connected graph G. Unspecified symbols and terms see [12] and [18].we had definition as follows:Definition 1 An L(2,1)-labeling of graph G is a function c:V(G)→{0,1,2,…,k}, for any u.v∈V(G),such that:(1) if d(u,v)=1.then|c(u)-c(v)|≥2;(2) if d(u,v)=2,then|c(u)-c(v)|≥1.A k-L(2,1)-labeling is an L(2,1)-labeling such that no label is greater than k.The L(2,1)-labeling number of G,denoted by A(G),is the smallest number k such that G has a k-L(2,1)-labeling.Then we can define the L(d,1)-labeling.Definition 2 An L(d,1)-labeling of graph G is a function c:V(G)→{0,1,2,…,k}, for any u,v∈V(G),such that:(1)if d(u,v)=1,then |c(u)-c(v)|≥d;(2)if d(u,v)=2,then |c(u)-c(v)|≥1.A k-L(d,1)-labeling is an L(d,1)-labeling such that no label is greater than k.The L(d,1)-labeling number of G,denoted by Ad(G),is the smallest number k such that G has a k-L(d,1)-labeling.(λ2(G)=λ(G)).The L(2,1)-labeling was first introduced by Jerrold Griggs and Roger Yeh in a paper in 1992.In this paper Griggs and Yeh solve the problem for specific types of graphs and make the following conjecture:If G is a graph with maximum degree△,then there is a proper L(2,1)-labeling of G with span at most△2.Since this paper there has been much research on the subject.Bounds have been proven for certain classes of graphs[2],[3].The best bound proven thus far for a general graph G with maximum degree△isλ(G)≤△2+△-2[4].Most recently,there was an article showing that for a graph G with sufficiently large maximum degree△,the conjectureλ(G)≤△2 holds,but exactly how large this△needs to be is not known[5].In the second chapter we studied the(d,1)-total-labeling of G.Whittlesey studied the L(d,1)-labeling of the first subdivision of a graph G.The first subdivision of a graph,the graph s1(G) obtained from G by inserting one vertex along each edge of G.An L(d,1)-labeling of s1(G)corresponds to a(d,1)-total-colouring of G.This colouring,which is introduced by Havet and Yu,is called(d,1)-total labeling.Definition 3 A(d,1)-total-labeling of graph G is a function c:V(G)∪E(G)→{0,1,2,…,k},such that:(1)for any u,v∈V(G),if uv∈E(G),then c(u)≠c(v)；(2)for any u,v,w∈V(G),if uv,uw∈E(G),then c(uv)≠c(uw)；(3)for any u,v∈V(G),if uv∈E(G),then |c(u)-c(uv)|≥d.The span of a(d,1)-total-labeling is the maximum difference between two la-bels.The(d,1)-total number of a graph G,denoted byλdT(G),is the minimum span of all (d,1)-total-labeling of G.Fredeic Havet and Min-Lin Yu provide the general lower and upper bounds forλdT(G).And they introduced the well-known (d,1)-Total Labeling Conjecture.That isλdT(G)≤min{△+2d-1,2△+d-1}.It was also shown thatλdT(G)≤2△(G)+d-1 for any graph G.Moreover,they conjectured the following.Conjecture. Let G be a connected graph.If△(G)≤3 and G≠k4,thenλ2T(G)≤5.In the second chapter we had the following theorems.Theorem 2.1.5 For any simple graph G,△(G)=△,if△is even and at least 8,thenλ2T(G)≤2△-1.Theorem 2.1.6 If G is a k regular graph,χ(G)≥t(t≥3),d> k+t-3,thenλdT≥d+k+t-2.Theorem 2.2.3 Let G be a planar graph with△≤3 and girth g≥18,thenλ2T(G)≤5.Theorem 2.2.4 Let G be a planar graph with△≤4 and girth g≥12,thenλ2T(G)≤7.Hajo Broersma has varied the classic vertex coloring and put the restrictions only on the backbone of G.This new kind coloring was called BackBone coloring.Sun Lei and Wang Huijuan relax the restrictions on the original graph to the spanning tree,put forward the concept of L(d,1)-T-labeling and L'(d,1)-T-labeling of graphs.In the third chapter we studied the L(d,1)-T-labeling.It has less restrictions than the L(d,1)-labeling and the restrictions are strengthened along the backbone.Given a spanning tree T of G,the transmitters of distance two must have the different chan-nels. Moreover,the adjacent transmitters must have the different channels.And the sepa-ration of the channels of transmitters which are adjacent in T has to be at least d.It's only strict in a backbone of G.We study the case where the backbone is a spanning tree.As any connected graph has a spanning tree,so we had definition as follows:Definition 4 Let G be a simple connected graph and T is a spanning tree of G.An L(d,1)-T-labeling of graph G is a function c:V(G)→{0,1,2,…,k},for any u,v∈V(G),such that:(1)if d(u,v)=1,then |c(u)-c(v)|≥1；(2)if dT(u,v)=1,then |c(u)-c(v)|≥d；(3)if dG(u,v)=2,then |c(u)-c(v)|≥1.A k-L(d,1)-T-labeling is an L(d,1)-T-labeling such that no label is greater than k.The L(d,1)-T-labeling number of G,denoted byλdT(G,T),is the smallest num-ber k such that G has a k-L(d,1)-T-labeling.G is callled a claw-free graph if G doesn't contain K1,3 as a subgraph induced.G is called a K1,t-free graph if G doesn't contain K1,t as a subgraph induced.For a graph G of order n,u∈V(G),if d(u)=n-1,then u is called a control vertex of G.The Mycielski graph is defined as follows.G is a simple graph,G=(V(G),E(G)),V(G) ={v1,v2,…,vn}.The vertex set and edge set of M(G),which is the Mycielski graph of G,are defined as follows.V(G)={v1,v2,…,vn,v'1,v'2,…,v'n,w},E(M(G))={v'iw|i= 1,2,…,n}∪{viv'j|vivj∈E(G)}∪{vivj|vivj∈E(G)}.In the third chapter we had the following theorems.Theorem 3.1 If M(G)is the Mycielski graph of the simple connected Graph G,the maximum degree of G is△,|G|=n(n≥2),T is any spanning tree of M(G),then:when n≤2△,λdT(M(G),T)≤2△2+2△+2d-2；when n>2△,λdT(M(G),T)≤(n2+n)/2+2d-2.Theorem 3.2.2 If G is a K1,t-free connected Graph(3≤t≤n),the maximum degree of G is△,|G|=n,T is any spanning tree of G,thenλdT(G,T)≤(t-2)(t-1)△2+△+2d-2.In the fourth chapter we studied the L'(d,1)-T-labeling.It has less restrictions than the L(d,1)-T-labeling.Given a spanning tree T of G,the adjacent transmitters must have the different channels.And the separation of the channels of transmitters which are adjacent in T has to be at least d.Moreover,the transmitters of distance two in T must have different channels(L(d,1)-T-labeling request that the transmitters of dis-tance two in G must have the different channels).We had definition as follows:Definition 5 Let G be a simple connected graph and T is a spanning tree of G.An L'(d,1)-T-labeling of graph G is a function c:V(G)→{0,1,2,…,k},for any u,v∈V(G),such that:(1)if d(u,v)=1,then |c(u)-c(v)|≥1；(2)if dT(u,v)=1,then |c(u)-c(v)|≥d；(3)if dT(u,v)=2,then |c(u)-c(v)|≥1.A k-L'(d,1)-T-labeling is an L'(d,1)-T-labeling such that no label is greater than k.The L'(d,1)-T-labeling number of G,denoted byλdT'(G,T),is the smallest num-ber k such that G has a k-L'(d,1)-T-labeling.In the fourth chapter we had the following theorems.Theorem 4 If M(G)is the Mycielski graph of the simple connected Graph G,the maximum degree of G is△(△≥2),|G|=n,then there is a spanning tree To of M(G),such that:when n≤2△-1,λdT'(M(G),T0)≤3△+2d-3；when n>2△-1,λdT'(M(G),T0)≤(3n)/2+2d-2.