The(3,1)-Total Labeling Of Sparse Graphs

The labeling problem of graphs is one of the most important problems in graph the-ory,this problem has a more extensive theoretical knowledge and very strong application background.The graph labeling problem arose from the channel assignment problem.Given some broadcasting stations,we need to assign radio frequency to broadcasting sta-tions,in order to avoid interference,if two stations are too close,then the separation of the channels assigned to them has to be at least two.Moreover,if two stations are close,then they must receive different channels.Inspired by this problem,Griggs and Yeh[1]introduced L(2,1)-labeling in 1992,it was a graph theory model of the channel assignment problem.This notion has been studied many times and gives many challenging problems.In 2000,G.J.Chang et.al.[2]extended it to the L(p,1)-labeling.Whittlesey et.al.[3]studied L(2,1)-labeling of first subdivision of a graph G.The first subdivision of a graph G is the graph s1((G)obtained by inserting one vertex to each edge of G.A L(p,l)-labeling of s1(G)corresponds to a(p,l)-total labeling of the original graph G.Definition 1[1]A k-L(2,1)—labeling of a graph G is a function f:V(G)?{0,1,· · ·,k},such that:(1)for any two vertices u,v,if d(u,v)= 1,then |f(u)-f(v)|? 2;(2)for any two vertices u,v,if d(u,v)= 2,then |f(u)-f(v)|? 1.The L(2,1)-labeling number of a graph G,denoted by ?(G),is the minimum number k such that G has a k-L L(2,1)-labeling.Analogously we extended to L(p,l)-labeling,we can also define the L(p,l)-labeling.Definition 2 A k-L(p,1)-labeling of a graph G is a function f:V(G)?{0,1,...,k},such that:(1)for any two vertices u,v,if d(u,v)= l,then |f(u)-f(v)| ? p;(2)for any two verticesu,v,if d(u,v)= 2,then |f(u)-f(v)| ? 1.The L(p,1)-labeling number of a graph G,denoted by ?p(G),is the minimum num-ber k such that G has a k-L(p,1)-labeling.Definition 3[4]A(p,l)-total labeling of a graph G is an assignment of integers to V(G)U E(G),there is a function f:V(G)? E(G)? {0,1,…,k},verifying:(1)for any two adjacent vertices u,v,|f(u)-f(v)| ? 1;(2)for any two adjacent edgese,e',|f(e)-f(e')| ? 1;(3)for any two incident vertex u and edge e,f|(u)-f(e)| ? p.We call such an assignment a(p,1)-total labeling of G.The span of a(p,l)-total la-beling is the maximum difference between two labels.The(p,1)-total number of a graph G is the minimum span and is denoted by ?Tp(G).It is easy to see that total colouring strengthened with an extra condition,that is,the labels of incident vertex and edge must differ by at least p in absolute value.The(p,1)-total labeling was introduced by Havet and Yu,this labeling has been studied in several papers.By generalizing total colouring conjecture,Havet and Yu con-jectured that ?Tp(G)? min{?(G)+2p-1,2?(G)+p-1},we call it(p,1)-total labeling conjecture.The maximum average degree of a graph G is the maximum value of the average de-gree of its all real subgraph,denoted by mad(G),mad(G)= max{2|E(H)|/|V(H)|? H(?)G}.We consider only finite,simple and undirected graphs in this paper.In this paper,we mainly discuss the planar graphs with girth and the maximum degree restrictions,the(p,1)-total labeling conjecture is true when ? = 3,p = 3.In the first chapter of this paper,we mainly introduced some concepts,terminologies,symbols.In the second chapter,we studied the(p,1)-total labeling problem,and our main results are as follows:Theorem2.1.4 Suppose that G is a connected planar graph with ?(G)? 3 and g(G)? 16.then ?T3(G)<8.Theorem2.1.5 Suppose that G is a connected graph with ?(G)<3 and mad(G)<9/4,then?T3(G)? 8.