| An L(2, 1)-labeling of a graph G is an assignment function f, from the vertex set V(G) to nonnegative integers, satisfying: (1) |f(u) — f(v)| ≥ 2, if uv ∈ E(G); (2) |f(u) — f(v)| ≥ 1, if d(u,v) = 2. The set of all L(2, 1)-labelling is denoted by (?)(2,1). The L(2, 1)-labeling number is defined as λ(G) = minmax{f(v) : v ∈ V(G)}, i.e, the minimum of span(f) over all L(2, 1)-labelings of G. The definition of L(2, 1)-labelling arose from the channel assignment problem. Suppose a number of stations are given, we ought to assign a channel to each station such that the interference is avoided. In order to reduce the interference, any two 'very close' stations must receive channels apart enough, and any two 'close' stations must receive different channels.In this thesis, we consider another parameter about the labeling, the edge span, denoted by β(G) = minmax{|f(u) — f(v)||uv ∈ v(G)}, where f ∈(?) (2,1) and the minimum running over all L(2,1)—labelings of G. At the same time, we have some results about the edge span of L(d, 1)—labeling and L(s, t)— labelling on some graphs, denoted by βd(G) and βs,t(G). If there is a restriction about the maximum labeling, we can get the other parameters, denoted by βd(G,λd).In Chapters 2, 3, 4, 5, we get some results on βd(G) of some special graphs, such as Cn, T, Kn1,n2,...,nk, the triantgular lattice A, the square lattice Λ, the hexagon lattice ▽, the wheel Wn, the strong product of Pn and choral graphs. For the hexagon lattice, wheel Wn, the strong product of Pn and choral graphs, we give β(G, λ) and βd(G, λd).
|
PDF Full Text Request