Some Graph Labeling Problems Associated With The L(d, 1) Labeling Of Graphs

Graph coloring problem is one of the important problems and an active research field in graph theory.Some scholars presented and studied a few coloring problems with different restrictions and one of the promotion of graph coloring problems is graph la-beling.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.The transmitters are represented by the vertices of a graph;two vertices are "very close" if they are adjacent and "close" if they are of distance two in the graph.Then we can define the L(2,1)-labeling.We only consider the simple connected graph G.Definition 1 An L(2,1)-labeling of graph G is a function c:V(G)→{0,1,2,…,k},such that:(1) for any u,v∈V(G),if d(u,v)=1,then|c(u)-c(v)|≥2;(2) for any u,v∈V(G),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λ(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},such that: (1)for any u,v∈V(G),if d(u,v)=1,then |c(u)-c(v)|≥d；(2)for any u,v∈V(G),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)).There are a considerable number of articles studying the L(2,1)-labeling.Most of these papers consider the values of A on particular classes of graphs.Griggs and Yeh[1] provided a upper bound△2+2△for a gener al graph with the maximum degree△.Later Chang and Kuo[2]improved the bound to△2+△.Recently,Kral and Skrekovski[3]re-duced the bound to△2+△-1.If G is a diameter 2 graph,thenλ(G)≤△2.The upper bound is attainable by Moore graphs.Thus Griggs and Yeh[1]conjectured that the best bound is△2 for any graph G with the maximum degree△≥2.Determinining the value ofλis proved to be NP-complete.The maximum degree of G is denoted by△(G),the minimum degree of G is denoted byδ(G),the distance of u,v in graph is denoted by d(u,v).In the second chapter we studied the(d,1)-total-labeling of G.Whittlesey stud-ied 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-labeling of G.Definition 3[5]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.We call such a function a(d,1)-total-labeling of G. 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.Let G be a graph with maximum degree△,a(d,1)-total-labeling in[0,q]is a d-good labeling if each vertex is assigned a label in[0,△+d-1]. A cut[A,B]of a graph G is a set of two induced subgraphs A and B of G such that(V(A),V(B))is a partition of V(G).The bipartite graph(A,B)is the graph with vertex set V(G)and edge set E(G)＼(E(A)∪E(B)).The edges of(A,B)are called the cut edges.A maximum cut[A,B]of G is a cut with the maximum number of cut edges.It was conjectured in[5]thatλdT(G)≤△(G)+2d-1 for any graph G,which ex-tends the well-known Total Coloring Conjecture.It was also shown in[5]thatλdT(G)≤2△(G)+d-1 for any graph G,λ2T(G)≤6 if△(G)≤3,andλ2T(G)≤8 if△(G)≤4.We would give the two results in the second chapter.Theorem 2.5 Let G be a graph with maximum degree△,if△is ever. and△≥10.Thenλ2T(G)≤2△-1.Theorem 2.6 Let G be a graph with maximum degree△≤3,if the vertices inci-dent to a maximum degree vertex have at most△-1 maximum degree vertices.ThenλdT(G)≤d+4.As a variation of the classical vertex labeling,Hajo Broersma[6]introduced the Backbone-coloring.He put restrictions on the assignment of frequency channels along the backbone.In the third chapter we studied the L(d,1)-T-labeling.It has less restrictions than the'L(d,1)-labeling and along the backbone the restrictions are strengthened.The adjacent transmitters and the transmitters of distance two must have the different chan-nels. And the separation of the channels of transmitters which are adjacent in any spanning tree of the graph G has to be at least d.We only strict in the spanning tree of the graph.Let G be a graph,it 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)-labeling of graph G is a function c:V(G)→{0,1,2,…,k),such that:(1)for any u,v∈V(G),if d(u,v)=1,then |c(u)-c(v)|≥1；(2)for any u,v∈V(G),if dT(u,v)=1,then |c(u)-c(v)|≥d；(3)for any u,v∈V(G),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λd,T(G),is the smallest number k such that G has a k-L(d,1)-T-labeling.We define:Tλd,T(G):=maxT{λd,T(G):G is a graph with spanning tree T.}G is called a claw-free graph if G doesn't contain K1,3.If V(K1,n)={v0,v1,…,vn}and△(v0)=n,then v0 is called a control vertex of G.G is a simple graph,V(G)={v1,v2,…vn).Let V(G[I2])={v1,v2,…,vn,v'1,v'2,…,v'n}, E(G[I2])={v'iv'j,v'iv'j,v'iv'j|v'iv'j∈E(G)},then G[I2]is called the vertex split graph of G[7].In the third chapter we had the following theorems.Theorem 3.1.1 Let G be a simple connected graph with maximum degree△.Then Tλd,T(G)≤△2+2d-2.Theorem 3.1.2 Let G be a simple connected graph with maximum degree△；if the vertices incident to a maximum degree vertex have at most△-1 maximum degree vertices.Then Tλd,T(G)≤△2+2d-3.Lemma 3.1.3 Let G be a simple connected graph with at least one edge.Then limd→∞(λd+1(G))/(λd(G))=1Theorem 3.1.4 Let G be a simple connected graph with at least one edge.Then limd→∞(Tλd+1,T(G))/(Tλd,T(G))=1Theorem 3.2.2 Let G be a connected claw-free graph,then Tλd,T(G)≤3/4△2+2d+ 1/2△-2.Theorem 3.2.3 Let G be a vertex split graph of G,△(G)=△.Then Tλd,T(G)≤2△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 and along the backbone transmitters must have the dif-ferent channels.The separation of the channels of transmitters which are adjacent in any spanning tree T of the graph G has to be at least d and the transmitters of distance two in T must have different channels.So 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)-labeling of graph G is a function c:V(G)→{0,1,2,…,k},such that:(1)for any u,v∈V(G),if d(u,v)=1,then |c(u)-c(v)|≥l； (2)for any u,v∈V(G),if dT(u,v)=1,then |c(u)-c(v)|≥d；(3)for any u,v∈V(G),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),is the smallest number k such that G has a k-L'(d,1)-T-labeling We define:Tλ′d,T(G):=maxT{λ′d,T(G):G is a graph with spanning tree T.}In the fourth chapter we had the following theorems.Theorem 4.1.1 Let G be a simple connected graph with maximum degree△.Then Tλ′d,T(G)≤2△+2d-3.Theorem 4.1.2 Let G be a simple connected graph with maximum degree△；if the vertices incident to a maximum degree vertex have at most△-2 maximum degree vertices,then Tλ′d,T(G)≤2△+2d-4.Theorem 4.2.1 Let G be a simple connected graph with maximum degree△.Then there is a spanning tree T0 of G,such thatλ′d,T0(G)≤2△+2d-4.Theorem 4.2.2 Let G be a simple connected graph with at least one edge.Then limd→∞(?)=1.Theorem 4.2.3 Let G' be a vertex split graph of G,△(G)=△,then there is a spanning tree T0 of G',such thatλ′d,T0(G)≤3△+2d-2.