The (p,1)-Total Labeling Of Graphs And The Problem Of Weak Adjacent-Vertex-Distinguishing Colouring Of Graphs

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.