L(p,1)-labeling And L(p,q)-edge-labeling Of Graphs With Restriction On Spanning Tree

The graph theory is a very active branch of applied mathematics in recent decades,andthe coloring problem of graphs is one of the most important parts in the graphs the-ory.Some classic coloring problems such as vertex coloring and edge coloring have beendeeply studied.Based on these,mathematicians have proposed some new meaningful col-oring problems.The coloring problems of graphs can be thought of as a special labelingproblem of graghs.And one of its theory research backgroud is the channel assignmentproblem[15].Given some transmitting stations,in order to avoid the mutual interferencebetween two tranmitting signals,we should assign channals to them meeting that: if twostations are too close,the channals assigned to them have to be separated at least two;twoclose （but not too close） stations should receive diferent channals.As a variation ofit,Griggs and Yeh put forward the L（2,1） labeling[25] and L（j, k） labeling.L（j, k） labelingis a kind of labelings for vertics. And J.P.Georges and D.W.Mauro first studied L（j, k） edge labeling problems in their paper[26].The first chapter of this paper mainly introduced some concepts,terminologies,symbolsand summarized the history and recent development of labeling problems of graphs.Termin-ology and notations unexplained follow[2].Definition1A proper k coloring of graph G is a positive integer assignment cto the vertex set V （G） such that the colors of any adjacent vertics in G are diferent.The smallest k such that G has a proper k coloring is the chromatic number ofG,denoted by χ（G）. Definition2A proper edge coloring of graph G=（V, E） is a positive integerassignment f to the edge set E（G） such that the colors of any adjacent edges in G arediferent.The smallest k such that G has a proper edge coloring is the edge-chromatic numberof G,denoted by χ′（G）.Hajo Broersma[16] introduced the Backbone-coloring.He restricted the restrictionsof the normal vertex coloring of original graph along the backbone. In this paper,werestrict some conditions of L（d,1） labeling and L（j, k） edge-labeling in the spanningtree of the graph.Further more,we proposed several labeling problems restricted in thespanning tree and gave the upper bounds of the labeling number of general graphs andseveral special graphs.Definition3[25]An L（d,1） labeling of graph G is a function c: V （G）â†'{0,1,2,..., k},sucthat:（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 λd（G）.Definition4[34]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 greaterthan k.The L（d,1） T labeling number of G,denoted by λd,T（G）,is the smallest numberk 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}.Definition5[34]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 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 greaterthan k.The L′（d,1） T labeling number of G,denoted by λ′d,T（G）,is the smallest numberk 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 second chater, we mainly got the following conclusions.Definition6Let G be a simple connected graph and T is a spanning tree of G.AnL（p,1T） labeling of graph G is a function c: V （G）â†'{0,1,2,..., k},such that:（1） For any u, v∈V （G）,if dG（u, v）=1,then|c（u） c（v）|≥p;（2） For any u, v∈V （G）,if dT（u, v）=2,then|c（u） c（v）|≥1.A k L（p,1T） labeling is an L（p,1T） labeling such that no label is greater thank.k is the smallest number such that G has a k L（p,1T） labeling. And k is called theL（p,1T） labeling number of G,denoted by λp（G）,we define:T_λp,1T（G）=maxT{λp,1T（G）: G is a graph and T is a spanning tree}.Theorem2.1.1For any simple connected graph G with maximum degree,â–³T isany spanning tree of G._{Tλp,1T（G）≤2pâ–³1.Theorem2.2.1For any simple connected graph G with maximum degree,â–³Tis any spanning tree of G. By the layered idea,T can be layered into several vertexsets,denoted X0, X1,, Xk.Let v be a vertice of X1, v1, v2,, vj（1≤j≤△-1） be itsadjent vertex,if G doesn’t have vertex of X0meeting the following condition:Vertex of X0are adjcent with vertex of X1on T,and dT（v）=dG（vj）=△（j=1,2,...â–³-1）,but there are not edges among v1, v2,...vâ–³1in G.then Tλp,1T（G）≤2p2.Theorem2.2.2Let G be a simple connected graph with maximum degreeâ–³,T isany spanning tree of G,and the adjacent vertices with maximum degree of G has at most â–³-2vertices with maximum degree, then Tλp,1T（G）≤2pâ–³-2.Definition7～[26]Given a simple graph G,j, k is positive integers,f: E（G）â†'{0,1,2,..., k} is a proper edge labeling such that:（1） for any e1, e2∈E（G）,if d（e1, e2）=1,then|e1e2|≥j;（2） for any e1, e2∈E（G）,if d（e1, e2）=2,then|e1e2|≥k.So f is called an L（j, k） edge labeling of G.An L（j, k） edge-labeling number of G is denoted by λ′j,k（G）=min{k|G has ak L（j, k） edge labeling}.In chapter3,we proposed several new definitions of edge labeling,and gave the upperbounds of the general graphs and several special graphs.Definition8Given a simple graph Gand T is a spanning tree of G,k is a positiveinteger,f: E（G）â†'{0,1,2,..., k} is a proper edge labeling such that:（1） for any e1, e2∈E（G）,if dG（e1, e2）=1,then|e1e2|≥p;（2） for any e1, e2∈E（G）,if dT（e1, e2）=2,then|e1e2|≥q.So f is called L（p, qT） edge labeling of G.An L（p, qT） edge-labeling number of G is denoted by λ′p,qT（G）=min{k|G has ak L（p, qT） edge labeling}.Definition9Given a simple graph Gand T is a spanning tree of G,k is a positiveinteger,f: E（G）â†'{0,1,2,..., k} is a proper edge labeling such that:（1） for any e1, e2∈E（G）,if dT（e1, e2）=1,then|e1e2|≥p;（2） for any e1, e2∈E（G）,if dT（e1, e2）=2,then|e1e2|≥q.So f is called L（pT, qT） edge labeling of G.An L（pT, qT） edge-labeling number of G is denoted by λ′pT,qT（G）=min{k|G has ak L（pT, qT） edge labeling}.Lemma3.1.1[10]For any tree T with maximum degree,△χ′1,1（T）≤2â–³-1, i.eλ′1,1（T）≤2â–³-2.Theorem3.1.2For any simple connected graph G with maximum degree,T is any spanning tree of G,λ′1,1T（G, T）≤3â–³-2.Definition10^[19]G is a simple graph.Let G=（V （G）, E（G））, V （G）={v1, v2,, vn}.M-ycielskian graph M （G） of G, the set of vertices and the set of edges are defined asfollows: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）}.From the definition we know that δ（M （G））=δ（G）+1,（M （G））=2（G） or（M （G））=nand for any vi∈V （M（G））, v′′i∈V （M（G））, dM （G）（vi）=2dG（vi）, dM （G）（vi）=2dG（vi）+1, dM （G）（w）=n.Mycielskian graph has important application in reseaching thecriticality of coloring of graph.Theorem3.1.3Let G be a graph of order n and with maximum degree.â–³M （G）is a Mycielskin graph of G.Then there is a spanning tree T such that:If n≤3â–³, λ′1,1T（M （G）, T）≤2△（M （G））}1; n>3â–³, λ′_1,1T（M （G）, T）≤34（M （G））)1.Lemma3.1.4For any tree T with maximum degreeâ–³,λ′p,1（T）≤2p（△-1）.Theorem3.1.5For any simple connected graph G witn maximum degree,T isany spanning tree of G,λ′p,1（T）≤3pâ–³-p-1.Lemma3.2.1[24]For any tree T with maximum degree, λ′_2T,1T（G, T）≤2+3.Theorem3.2.2For any simple connected graph G with maximum degree,T isany spanning tree of G,λ′_2T,1T（G, T）≤3â–³+3.Definition11[33]If a simple G=（V （G）, E（G））, V （G）={v₁, v₂,, v_n},the vertexset and edge set of G′is definited as follows:V （G′）={v₁, v₂,, v_n, v′₁, v′₂,, v′_n}, E（G′）={v′ivj, v_ivj, v′′iv′j, v_ivj|v_ivj∈E（G）},thenG′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 v∈V （G′）, d_G′（v）=2d_G（v）.Theorem3.2.3Let G′be a vertex split graph of graph G,then there is a spanningtree T′of G′such that λ′_2T,1T（G, T′）≤2△（G′）+3.Theorem3.3.1For any simple connected graph G with maximum degree,T isany spanning tree of G,λ′_pT,1T（G, T）≤（2p+1）（△-1）+1.Definition12[30]Let G₁, G₂be the simple graphs,if|G₁|=n₁,V （G₁）={u1, u2,, un₁};|G₂|=n2,V （G₂）={v₁, v₂,, vn2}, we define the vertex set and edge set of the carte-sian product graph of G₁, G₂,i.e G₁×G₂as follows:V （G₁×G₂）={u_iv_j|i=1,2,, n₁, j=1,2,, n2};E（G₁×G₂）={（u_iv_j）（ukv_l）|v_j=v_land （u_iuk）∈E（G₁） or u_i=ukand （v_jv_l）∈E（G₂）, i, k=1,2,, n₁, j, l=1,2,, n2}.The cartesian product graph G₁×G₂and the original graph satisfy the relatongship:（G₁×G₂）=△（G₁,△（G₂））.Theorem3.3.2For the simple connected graph G₁, G₂,the maximum degree sat-isfy:△（G₁）≤△（G₂）,then there is a spanning tree T of the cartesian product graph suchthat λ′_pT,1T（G₁×G₂）≤（2p+1）△（G₁）+△（G₂）+1.