| Graph coloring problem is one of the most important problems in graph theory, and one of its promotions is the graph labeling problem. The graph labeling prob-lem arose from the channel assignment problem. Given some broadcasting stations. These stations use different channels to transmit signals. In order to avoid interfer-ence, any two stations that are very close must use frequencies far enough, and any two close station must use different frequencies. We assign channels to each station such that the interference is avoided and we can use the least channel resources.Inspired by this problem, Griggs and Yeh[3] introduced L(2,1)-labeling. In2000, G.J.Chang et. al.[5] extended it to the L(p,1)-labeling. This labeling problem has been studied in many articles so far. Whittesey et. al.[6] studied the L(2,1)-labeling of first subdivision of graph G. The first subdivision of graph G is the graph S1(G) obtained from inserting one vertex to each edge of G. A L(p, l)-labeling of S1(G) corresponds to a (p,1)-total labeling of the original graph G.Definition1.2.1[3]A k-L(2,1)-labeling of graph G is a function f:V(G)→{0,1,..., k} such that:(1)for any two vertices u,v V(G), if d(u,v)=1, then|f(u)-f(v)|≥2;(2)for any two vertices u, v E V(G), if d(u,v)=2, then|f(u)-f(v)|≥1.The L(2,1)-labeling number of graph G, denoted by λ{G), is the minimum number k such that G has a k-L(2,1)-labeling.Analogously, we can define the L(p,1)-labeling. Definition1.2.2[5] A k-L(p,1)-labeling of graph G is a function f:V(G)→<0,1,…,k)such that:(1)for any two vertices u,v∈V(G),if d(u,v)=1,then|f(u)-f(v)|≥p；(2)for any two vertices u,v∈V(G),if d(u,v)=2,then|f(u)-f(v)|≥1.The L(p,1)-labeling number of graph G,denoted by λp(G),is the minimum number k such that G has a k-L(p,1)-labeling.Definition1.2.3[3] The(p,1)-total labeling of graph G is an assignment of integers to V(G)and E(G),i.e.there is a mapping f:V(G)∪E(G)→{0,1,…,k} such that:(1)for any two adjacent vertices u and v,we have|f(u)-f(v)|≥1；(2)for any two adjacent edges e and e’,we have|f(e)-f(e’)|≥1；(3)for any two incident vertex u and edge e,we have|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 maximum different between two labels.The minimum span of a (p,1)-total labeling of G is called the(p,1)-total number and is denoted by λTp(G). It’s not hardly to see that the (p,1)-total labeling problem is a total coloring problem that conditions are strengthened,that is,the labels of incident vertex and edge must differ by at least p.The maximum average degree of graph G,denoted by mad(G),is the maximum value of the average degree of all its real subgraph,mad(G)=max{2|E(H)|/|V(H)|,H (?) G}.In the second chapter,we studied the(p,1)-total labeling problem,and our main results are as follows:Theorem2.1.4Suppose that G is connected planar graph with△(G)≤3and mad(G)<9/4,then λT2(G)≤5. Theorem2.1.5Suppose that G is connected planar graph with△(G)≤4and mad(G)<5/2,then λT2(G)≤7.Definition2.2.1[24] Let G be a connected graph with V(G)={v1,v2,...,Vn]. Let G’be a coPy of G with V’(G)={v’1,v’2,…,v’n}.A new graph D(G)is defined as following:V(D(G))=V(G)∪V’(G),E(D(G))=E(G)∪E(G’)∪{v1v’1,v2v’2,…,vnv’n}.Theorem2.2.5Let Cn be a cycle,then λTp(D(Cn))=p+3,if n三0(mod2)； and p+3≤λTp(D(Cn))≤p+4,if n≡1(mod2).Definition2.2.2[25] Let Fm be a fan and its order is m+1.We denote the new graph by Cn·Fm when n hearts of fan are connected into a cycle,that is,V(Cn)={v1,u2,…,vn),V(Cn·Fm)=V(G)∪u{uij|j=1,2,…,n；j=1,2,…,m},E(Cn·Fm)=E(Cn)∪{viuij|i=1,2,…,n；j=1,2,…,m)∪{uijuij+1|i=1,2,...,n；j=1,2,...,m-1}.Theorem2.2.7If n is even,p≥2,then λTp(Cn·Fm)=p+3when m=1；and m+p+1≤λTp(Gn·Fm)≤m+p+2when m≥2.Definition2.2.3[27] Let G and G’be two simple graphs with vettex sets V(G)={u1,u2,...,un)and V(G’)={v1,v2,…,vn).We add the following matchings be-tween G and G’:uivi,uivi+1,uivi+2,…,uivi+m,...,uivi+(n),i=1,2,…,n；m=0,1,2,…,n；when i+m>n,i+m is the faddition in the sense of mod n.The series of graphs obtained by this way,denoted by G(1)n,n,G(2)n,n; G(n)n,n,are called the weak join of graphs G and G’.Theorem2.2.9Let Pn be a path of order n,then m+p+2≤λTp(P(m+1)n,n)≤ m+p+4,m=0,1,2,…,n-2,n≥4.Theorem2.2.11Let Cn be a cycle of order n,if n is even,then m+p+3≤λTp(C(m+1)n,n)≤m+p+5,m=0,1,2,…,n-1.Theorem2.3.6Let G be a planar graph with maximum degree△(G),if the induced subgraph of maximal degree vertex of G contains odd cycle,then λTp(C)≥△(G)+p.Theorem2.3.7Let G be a planar graph with maximum degree△(G),if the induced subgraph of maximal degree vertex of G is r-regular,and△(G)一p<r, then λTp(C)≥△(G)+p.In the channel assignment problem,the following situation occurs:If the re-ceived frequency band of some transfer stations are broken or uncontrolled,we can allow some labcling vertices unrestricted.To solve this problem,we studied the im-proper labeling problem.Here,we give the definition of improper labeling.Definition3.1.1[28] For positive integers p,q,r,s with p≥q,the improper (r,s,p,q)-labeling of a graph G is an integer assignment L to the vertex set V(G) sueh that:(1)If d(u,v)=1,then for each u∈V(G),at most r neighbors of u receive labels satisfying:|L(u)-L(v)|<p and for the remaining vertices in{v|d(u,v)=1},we have|L(u)-L(v)|≥p.(2)If d(u,v)=2,then for eachu∈V(G),at most s vertices in{u|d(u,v)=2}receive labels satisfying:|L(u)-L(v)|<q and for the remaining vertices in {v|d(u,d)=2),we have|L(u)-L(v)|≥q.The span of an improper(r,s,p,q)-labeling is the maximum difference between twe labels. The minimum span taken over all improper(r,s,p,q)-labeling of graph of G is called the λ(r,s)(G；p,q)number and denoted by λ(r,s)(G；p,q).Without loss of generality,the minimum label of improper(r,s,p,q)-labeling of G is0. If for two adjacent vertices u and v we have|L(u)-L(v)|<p,then v is a bad vertex of u.On the other hand,u is a bad vertex of v.If u and v are distance two apart,we have|L(u)-L(v)|＜q,then v is a bad vertex of u.On the other hand, u is a bad vertex of v.If for any two bad vertex u and v, we have L(u)=L(v).Then we call such an improper(r,s,p,g)-labeling of graph G an improper(r,s,p,q)’-labeling.And the (r,s,p,q)’-labeling number is denoted by λ(r,s)(G；p,q).In the third chapter of this paper,we mainly get the following results:Theorem3.1.3Suppose that G is a planar graph with the maximum degree△,if G does not contain cycles of length from4to9,(p,q,r,s are positive integers, p≥q),then λ(r,s)(G；p,q)≤(2q-1)(△-r-s)+4p+4q-4. |
