L(d, 1)-Labeling Of Graphs

All graphs considered in this paper are finite simple graphs.For a graph G,we denote its vertex set,edge set and maximum degree by V(G),E(G) andΔ(G) respectively. A k-L(d,1)-labelling of a graph G is a function f from its vertex set V(G) to the label set {0,1,…,k} such that |f(x)-f(y)|≥d if z and y are adjacent,and |f(x)-f(y)|≥1 if x and y are at distance 2.The L(d,1)-labelling numberλ_d(G) of G is the smallest k such that G has a k-L(d,1)-labelling.The L(2,1)-labelling of a graph arose from a variation of the Frequency Channel Assignment problem introduced by Hale.This subject has been studied rather extensively in recent years.In 1992,Griggs and Yeh conjectured thatλ₂(G)≤Δ₂(G) for any graph G withΔ(G)≥2.The best known upper boundΔ²(G) +Δ(G) - 2 forλ₂(G) was established by Goncalves.In this thesis,we consider the L(d,1)-labelling for some graphs.In Chapter 1,we collect some basic notions used in the thesis and give a chief survey on this direction.In Chapter 2,3,4,5,we study the labeling problem of 2-outerplanar graphs,Generalized Petersen graphs,Planar grids,Triangular grids.Our main results in the present paper are as follows:(1) Forevery 2-outerplanar graph G,λ₂(G)≤Δ(G) + 12.(2) For every Generalized Petersen graph P(G),if d≥3 and n≥3,thenλ_d(P(n))≤3d + 3.(3) Characterize the L(d,1)-labelling number of planar grids and triangular grids.