Full-colorable Graphs And Optimal Label

The graph coloring problem is one of the most basic and important problems in graph theory. Graph labeling problem is an extension of the graph coloring problem, and there are extensive applications in true life.In this thesis , we will discuss two kinds of graph labeling problems: L(2,1)-labeling and optimal label.For a graph G, a L(2, 1)-labeling of G is a function f: V(G) → {0,1,2, …} such that:where d_G(u, v) is the distance of u and v in G. A k - L(2, 1)-labeling is a L(2, 1)-labeling such that no label is greater than k. The L(2, 1)-labeling number, denoted by λ(G), is the minimum k such that G has a k - L(2, 1)-labeling. In particular, if the labels are used consecutively, then it is called a No-hole L(2, 1)-labeling of G. The No-hole L(2, 1)-labeling number of G, denoted by λ|-(G), is the minimum k such that G has a No-hole k - L(2, 1)-labeling. It is obvious that λ|-(G) ≥λ(G). If a graph G satisfies λ(G) =λ|-{G), then it is called a full-colorable graph, otherwise it is called a non-full-colorable graph. In chapter 2, we will give some full-colorable graphs, the main results include:(1): The basic structure of non-full-colorable graphs. (2): If G is a graph with n vertices and m edges such that m ≤ n - 2, then G is afull-colorable graph except G≌ K₂, where k = n/2 ≥ 2. (3): If G is a graph with n verticesand the number of components C(G) ≥[(n+1)/2], then G is a full-colorable graph. (4): If G is agraph with n vertices and m edges such that m = n -1, then G is a full-colorable graph except G ≌K_1,n-1, K_1,3 ∪ aC₃ ∪ bC₆(a + b ≥ 1), K₁∪aC₃∪bC₆(a + b ≥ 1). (5): If G is a graph with n vertices and the number of components C(G) ≥[n/2] . then G is a full-colorable graph except G ≌K_k+1 ∪ (k - 1)K₁, where k=n/2.The L(2, 1)-labeling problem has been deeply studied in recent ten years. J.R.Griggs and R.K.Yeh ([19]) gave the value of λ(G) for some special classes of graphs such as pathes, cycles, trees and so on. They also proved that λ(G) ≤△² + 2â–³ for any graph with maximum degree A and conjectured that λ(G)≤ â–³² for any graph with maximum degree △≥ 2. G.J.Chang and D.Kuo ([2]) proved that λ(G) < â–³² + A for any graph with maximum degree â–³. Moreover, D.Kr á 1 and R.Skrekovski ([23]) slightly improved this bound by showing λ(G) ≤△² +â–³ - 1 for △≥ 2. Further improvement is given by Concalves in a recent manuscript, he showed that λ (G) ≤ â–³² + â–³ - 2 for â–³ ≥ 3. Up to now, we have found that many special graphs satisfy the conjecture λ(G) ≤ â–³². In chapter 3, we will give some upper bounds for some special graphs including Mycielski graphs and claw-free graphs. In addition, we study the upper bound and lower bound of the sum of λ(T) and λ(T^c), where T is a tree.A labeled graph is an ordered pair (G, L) consisting of a graph G and its labeling L : V(G) →{1,2,…, n), where n = |V(G)|. An increasing nonconsecutive path in a labeled graph (G, L) is either apath u₁u₂…u_k (k ≥ 2) in G such that L(u_i)+2 ≤ L(u_i+1) for all i = 1,2,…, k-1 or k - 1. The total number of increasing nonconsecutive paths in (G, L) is denoted by d(G, L). A labeling L is optimal if the labeling L produces the largest d(G, L). The optimal label was firstly proposed by M.L.Gargano, M.Lewinter and J.F.Malerba ([11]). They proposed an open problem: Give a label to P_n which makes d(P_n, L) maximum. Later, I.E.Zverovich solved this open problem. In chapter 4, we will give a simple proof for this problem and extend this problem to cycles and stars.