L(2, 1)-Labelings Of Composite Graphs

An L(2,1)-labeling of a graph G is an assingment f, from the vertex set V(G) to nonneg-ative integers, satisfying:(1)|f(u)- f(v)|≥2, if uv ∈ E(G);(2) |f(u)-f(v)| ≥ 1, if d(u,v) = 2. The L(2,1)-labeling number is defined as, λ(G) = min_fmax{f(v) : v ∈ V(G)}, i.e, the minimum span of f over all L(2,1)-labelings of G. The definition of X(G) arose from the channel/radio assignment problem. Suppose a number of stations are given. We ought to assign a channel to each of the given stations 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 practice , one stations may have more than one channels. We set up a model called composite graph G[H_v1,H_v2,…, H_vm] for this case. The vertices of G stand for the stations and the vertices of H stand for the channels. In this thesis, we foucus on the A value of composite graph with H_v1, H_v2,…, H_vm satisfying some conditions. In Chapter2, we give the definition and properties of composite graph G[H_v1, H_v2,…, H_vm], and give the way to label the subgraphs H_vi. Then we can prove that λ(G[H_v1, H_v2,…, H_vm]) = λ(G[H_vi] = λ{G[K_n^c) if each H_i has the same number n of vertices and has no hole. In Chapter 3, we determine the the L(2,1)-labeling number of P_m[K_n^c] where P_m is the path on m vertices. Then we prove that the λ{T[K_n^c) for any tree T and any integer n ≥ 1 is (△ + 1)n or (△ + 1)n + 1, where A is the maximum degree of T. We also investigate the case when the number of H_vi is not the same. Finally, we determine the A value of C_m[K_n^c] for m < 7,m = 8,m = 3k for integer k ≥ 3. We also show that...