L(1,d)-labeling On Several Kinds Of Graphs

For any vertex u,v in the graph,d(u,v)represents the distance between two vertices u,v in graphG.For a positive real numberm,an m-L(1,2)-labeling of a graph G is a mapping f:V(G)→[0,m]such that |f(u)-f(v)|≥1 if d/(u,v)=1,and |f(u)-f(v)|≥2 if d(u,v)=2.The L(1,2)-labeling number of G,denoted by λ1,2(G)is the minimum span over all L(1,2)-labelings of G.For a positive real number σ,let S(σ)denote the circle obtained from the closed interval[0,σ]by identifying 0 and σ into a single point.S(σ)is called a σ-cycle.For any x∈R,[x]σ ∈[0,σ]denotes the remainder of x upon division of σ.The circular distance of two points p and q on S(σ)is defined as |p-q|σ=min{|p-q|,σ-|p-q|}.A circularσ-L(1,2)-labeling of G is a function f:V(G)→[0,σ)satisfying |f(x)-f(y)|σ≥1 if d(x,y)=1 and |f(x)-f(y)|σ≥2 if d(x,y)=2.The minimum σ such that there exists a circular σ-L(1,2)-labeling of G is called the circular L(1,2)-labeling number of G and is denoted by σ1,2(G).The k-th power Gk of an undirected graph G is a graph with the same set of vertices and an edge between two vertices when their distance in G is at most k.Specially,G2 is called the square of G.For integers k and n satisfying 1≤k≤n-1,2k≠n,one defines the generalized Petersen graph P(n,k)with vertex set V(P(n,k))={u0,u1,…,un-1;v0,v1,…,vn-1}and the set of edges E(P(n,k))consisting of all those of the form[ui,ui+1],[ui,vi],[vi,vi+k],where i is an integer.Subscripts i+1,i+k in this note are to be taken modulo upon n.In this paper,we determine the L(1,2)-labeling numbers and the Circular L(1,2)-labeling numbers of square of cycles Cn,where n≥3.And determine the L(1,2)-labeling numbers of generalized Petersen graphs P(n,n-1/2),where n is odd integer.