The Vertex Labeling On Graphs

For a given graph G , an Z,(2,1) - labeling is defined as a function f : V(G)→ {0,1,2, …} such that:where d_G(u,v) denotes the distance between u and v. The elements in f(V(G)) are said to be labels. A k - L(2,1) - labeling is an L(2,1)—labeling such that no label is greater than k. The L(2,1) - labeling number of G , denoted by λ(G), is the smallest number k such that G has a k- L(2,1) - labeling . The No-hole L(2,1) - labeling is a variation of L(2,1) - labeling under the condition that the integers used are consecutive. The No-hole L(2,1) - labeling number of G is denoted by (λ|-)(G).By the above definitions, we can easily know that λ(G) ≤ (λ|-)(G) ≤n-1 for any graphs of order n if G admits a No-hole L(2,1) - labeling. Many efforts have been done to build the existence of No-hole L(2,1) - labeling and search the classes of graphs with (λ|-)(G) = λ(G). In Chapter 2, we pay our attention to the right hand of the above inequation. The main results include: (i) Let G be a simple graph of order n and size m . If m ≤ n - 2 or p(G) ≥ 「(n +1) / 2」 or G is connected and its diameter d≥ 「n / 2」+1, then G~chas a Hamilton path and and hence G has a No-hole Z(2,1) - labeling, (ii) Let G be a simple graph of order n and size m . If (λ|-)(G) = n-1, then n-2≤m≤(n- 1){n - 2) / 2. Moreover for any two integers n, m with n ≥ 3 and n-2≤m≤(n- 1)(n - 2) / 2, there exists a simple graph G of order n and size m with (λ|-)(G) = n -1. And the graphs with size n - 2 and (n - 1)(n - 2) / 2 are determined, (iii) Let G be a simple graph of order n. If (λ|-)(G) = n-1, then p(G) <「n / 2」, where p(G) denote the number of components of G. Moreover for any two integers n, p with n ≥ 4 and 1 ≤ p ≤ 「n / 2」, there exists a simple graph G of order n and p(G) = p with (λ|-)(G) = n -1. And the graphs G with p(G) =「n / 2」 are determined, (iv) Let G be a connected graph of order n≥ 6 and...