Map Labeling Problem

All graphs considered in this paper are finite simple graphs.Let G=G(V(G),E(G),ψ_G)be a graph,where V(G)≠φand E(G)denote the vertex set and edge set of G,ψ_G is an incidence function that associates each edge of G with an unordered pair of vertices of G.A graph is said to be embeddable in the plane,or planar,if it can be drawn in the plane so that its edges intersect only at their ends.Such a drawing of a planar graph G is called a planar embedding of G.We therefore sometimes refer to a planar embedding of a planar graph as a plane graph.A plane graph G partitions the rest of the plane into a number of connected regions;the closures of these regions are called the faces of G.If v∈V(G),we use d_G(v)stand for the degree of v in G.Let△(G)andδ(G)denote the maximum and the minimum vertex degree of G.A walk in G is a finite non-null sequence whose terms are alternately vetices and edges,if the vertices of walk are distinct,then the walk is called a path.A walk is closed if it has positive length and its origin and terminus are the same.A closed trail is a cycle.A cycle of length k is called a k-cycle.The degree of a face f in G(written r(f))is the number of edges of G incident with f.An L(p,q)-labelling of graph G is a function f from the vertex set v(G) to the set of all nonnegative integers such that for each x,y∈V(G),|f(x)-f(y)|≥p if d_G(x,y)=1 and |f(x)-f(y)|≥q if d_G(x,y)=2.A k-L(p,q)-labelling is an L(p,q)-labelling such that no label is greater than k.The L(p,q)-labelling number of G,denoted byλ(G;p,q),is the smallest number k such that G has a k-L(p,q)-labeling.If q=1,The L(p,q)-labelling is L(d,1)-labeling of G,and L(d,1)-labeling number denoted byλ(d,1);If d=2,The L(d,1)-labelling is L(2,1)-labelling of G,denoted byλ(G).An(d,1)-total labelling of G corresponds to an assignment of integers to V(G)∪E(G),such that any two adjacent vertices of G receive distinct integers,any two adjacent edges of G receive distinct integers,and a vertex and an edge incident receive intergers that differ by at least d(d≥2).The width of the minimum range of labels required for a such labelling of G is called the(d,1)-total labelling number and denoted byλ_d^T(G).L(2,1)-labelling was first considered and conjectured thatλ(G)≤△² for any simper graph by Griggs and Yeh in[8].in this paper,We studied the problem of L(2,1)-labelling on self-complementary graphs,and proved thatλ(G)≤2△for self-complementary graphs.J.V.D.Heuvel and S.McGuinness[11]have proved thatλ(G,p,q)≤(4q-2)△+10p+38q-24 for any planar graphs G with maximum degree△. in this paper we also studied the upper bound ofλ_p,q-number of some planar graphs, it is proved thatλ(G;p,q))≤(2q-1)△+2(2p-1)if G is an outerplanar,andλ(G;p,q)≤(2q-1)△+6p-4q-1 if G is a Halin graph,we considered the L(p,q)-labeling number on planar graphs with high maximum degree,and proved thatλ(G;p,q)≤(2q-1)△+6(p-q)for h₁-graph andλ(G;p,q)≤(2q-1)△+8p-6q-1 for h₂-graph.In the paper,we studied the labelling and total labelling of particular planar graphs.The paper is divided into four chapters.In Chapter One,we introduced some basic conceptions of graph theory,the primary results about the theory of labelling and the several results of the paper.In Chaper Two,we discussedλ(d,1)-number of every generalized Petersen graphs and L(2,1)-labelling on self-complementary graphs.In Chaper Three,we discussed the L(p,q)-labelling number of particular planar graphs.In Chaper four,we discussed the total labelling number of some bipartite graphs.The main results are the following theorems. Theorem 1:Let G∈PG(n),thenλ(G)=3d+3 if G is isomorphic to PG (Fig.2.1.2).Otherwise,λ_d(G)≤4d.Theorem 2:L(2,1)-labelling number of self-complementary graphs is proved thatλ(G)≤2△Theorem 3:Let G be a Halin graph with maximum degree△,thenλ(G;p,q)≤(2q-1)△+6p-4q-1.Theorem 4:Let G be an outerplanar graph withδ(G)≥2,thenλ(G;p,q)≤(2q-1)△+2(2p-1)Theorem 5:Let G be an h₁-graph with |V(G)|≥2,thenλ(G;p,q)≤(2q-1)△+6(p-q)Theorem 6:Let G be an h₂-graph with |V(G)|≥9,thenλ(G;p,q)≤(2q-1)△(G)+8p-6q-1Theorem 7:Let d≥2,each grid G_m×n,with m≥4,n≥5,is type 2.Theorem 8:Each grid G_m×n,with m=3,n=5, if d≥3,is type 2. if d=2,is type 1.Theorem9:Each grid G_m×n,with m=4,n=4, If d≥3,is type 2. if d=2,is type 1.Theorem 10:Let d≥3,,G_3×3and G_3×4are type 2.Theorem 11:Let d≥2,each grid G_m×nwith m=2,n≥4,is type 2.Theorem 12:Grid G_m×nwith m=2,n=3 if d=2,is type 1. if d≥3,is type 2.Theorem 13:Let d≥2,grid G_2×2is type 2.Furthermore,in the last part of the paper we list some problems for future research.