L(2,1)-Edge-Labeling Of Graphs

Distance two labeling (or L(2,1)—labeling) is motivated by the channel assignment problem. It is an assignment of nonnegative integers to the vertices such that (1) |f(u) — f(v)|≥ 2 if uv ∈ E(G), and (2)|f(u) - f(v)| ≥ 1 if d(u,v) = 2. The L(2,1)-labeling number of G is defined as λ(G) = min_f max{f(v) : v ∈ V(G)}. The channel assignment problem is the assignmet of channels to television transmitters such that any two 'very close' stations must receive channels apart enough, and any two 'close' stations must receive different channels. We ought to minimize the span of a channel assignmet without the interference.This thesis considers L(2,1)-edge-labeling of G. It is a mapping f from edge set E(G) into nonnegative inegers such that (1) |f(e₁) - f(e₂)| ≥2, if edges e₁ and e₂ are adjacent; (2) |f(e₁) -f(e₂)| ≥ 1, if the distance between e₁ and e₂ is 2. The L(2, 1)-edge-labeling number is defined as, λ_e(G) = min_fmax{f(e) : e ∈ E(G)}, i.e, the minimum of span (f) over all L(2, 1)-edge-labelings of G. Let L(G) be the line graph of G, then it is easy to see that λ_e(G) = λ(L(G)).In 1992, Griggs and Yeh conjectured that λ(G) ≤ Δ²(G) for any graph. However, this conjecture has not been proved till now. In Chaper 2, we present lower and upper bounds on λ_e interms of the maximum degree for general graphs, and show that λ(L(G)) ≤ [(Δ_L²)/2 +2Δ_L-1] ≤ Δ_L², which implies that all line graphs are consistent with the conjecture of Griggs and Yen.In Chapters 3 and 4, we determine the λ_e—numbers for wheels, complete graphs, complete bipartition graphs and some complete r—partite graphs, and get the low and upper bounds for trees and unicycles. Furthermore, we provide a sharp bound for some composite graphs.Chapter 5 studies the λ_e—numbers for 3-regular graphs. We investigate the edge-labeling of Cubic Halin graphs and generalized Petersen graphs, and give the bounds on λ_e for these graphs. Moerover, we obtain that the edge-labeling number of the Petersen graph is 8.