| Graph theory originated from the 30's of 18th century.In 1736,Euler solved the problem of seven bridges of konigsberg,the graph theory was born.Along with the de-velopment of graph theory,the method in this field has a wide application in chemical biology,information theory,network theory,control theory and computer science.The coloring problems of graphs have received wide concern as one of the most classic prob-lems in graph theory.Starting with the famous four-colour conjecture,a series of new problems,such as vertex colouring,edge colouring,total colouring,list coloring,channel coloring have been produced successively.They have a wide application in actual living world.In this paper,all graphs considered are finite,simple and connected graphs.A graph G is planar if it can be be embedded in the plane so that its edges intersect only at their ends.We use V(G),E(G)to denote the vertex set,the edge set.We usually denote the number of V(G),E(G)by |V(G)|,IE(G)].G'=(V',E')is called a subgraph of G=(V.E)if V' C V,E'(?)E,denoted by G'(?)G.We usually add or remove some vertices and edges to construct new graphs.If V'(?)c V(G),we obtain a graph G-V' by deleting from G the V' together with all the edges incident with V'.If E(?)E(G),we obtain a graph G-E' by deleting E' from G but leaving the vertices and the remaining edges intact.The degree of a vertex v in a graph G,denoted by dG(v)or d(v),is the number of edges of G incident with v.We denote by ?(G)and ?(G)the minimum and the maximum degree of the vertices of G,and denote by d(f)the degree of a face f,which is the number of edges of G incident with f.Channel assignment problem is an optimization problem of how to assign radio channel resources to achieve the most reasonable application.In the channel assignment problem,we want to avoid interference between the transmission signals.If the two sites are very close,these frequency differ by at least 2.If the two sites are close,the assigned frequency just be different.Inspired by the problem,Griggs and Yeh[10]introduced the L(2,1)-labelling and extended it to the L(p,1)-labelling.An L(p,q)-labelling of G corresponds to an assignment of integers to V(G)such that:if u and v are adjacent in graph G,then |f(u)-f(v)|? p;if u and v are 2 apart,then |f(u)-f(v)|? q.The incidence graph of a graph G is the graph obtained by replacing each edge of G by path of length 2.Havet[6,7]defined the L(p,1)-labelling problem of incidence graph as the(p,1)-total labelling problem of graph,which can be regarded as a generalization of total coloring.Graph G has a k-(p,1)-total labelling if there is an assignment f of {0,1,2,...,k})to V(G)U E(G)such that:(1)For any two adjacent vertices u and v of graph G,we have |f(u)-f(v)|? 1;(2)For any two adjacent edges e1 and e2 of graph G,we have |f(e1)-f(e2)|?1;(3)For any two incident vertex u and edge e,we have |f(u)-f(e)|?p.The minimum span of a(p,1)-total labeling of G is called the[p,1)-total number and denoted by ?pT(G).Havet?Yu[8]have the following(p,1)-total labelling conjec-ture:Conjecture 1.3.3[6,8]If G is a simple graph with maximum degree ?.then ?pT(G)??+2p-1 or ?pT(G)?min{?+2p-1,2? +p-1}.The important results about(p,1)-total labelling number and(2,1)-total la-belling number are as follows.Theorem 1.3.4[1]If G is a simple graph,then max{r(?(G)-1)+1,s(?'(G)-1)+1,t+1} ??r,s,t(G)?r{?{G)-1)+s(?'(G)-1)+t+1.Theorem 1.3.10[19]Let G be a planar graph with maximum degree ? and p? 2,p ?Z.If ?? 4p+4,then ?pt??+2p-2.Theorem 1.3.13[22]If G is a planar graph,??12?then ?+1??2T(G)??+2.Theorem 1.3.14[23]If is a planar graph without k-cycle and ??9,k?{3,4,5,6},then ?2T(G)??+2.We discuss the(2,1)-total labelling number of some planar graphs in this paper.The second chapter is the main part of this paper,we give the(2,1)-total labelling number of a planar graph G with restricted conditions and ?=11,10,9.In the third chapter,we give the(2,1)-total labelling number of a planar graph G with restricted conditions and ?=8,7,6,we gived two different proofs based on whether we use the four-colour theorem.In this paper,we prove the following theorems.Theorem 2.1.1 If G is a planar graph with maximum degree 11 and 3-cycle is not adjacent to the A-cycle,k? {3,4},then ?2T{G)??+2.Theorem 2.1.2 If G is a planar graph with maximum degree 10 and 3-cycle is not adjacent to the k-cycle,k?{3,4},then ?2T[(G)??+2.Theorem 2.1.3 If G is a planar graph with maximum degree 9 and 3-cycle is not adjacent to the k-cycle,k ?{3,4,5},then ?2T(G)??+2.Theorem 3.2.1 If G is a planar graph without 5-cycle and 6-cycle.?(G)=p+5,then ?2T(G)??+5,p=1,2,3... |
PDF Full Text Request