The Circular Labeling Of Graphs

Graph theory is a subject with lots of applications. The vertex-labeling problem is one of the most basic and important problems in graph theory. And there are extensive applications in the true life. The study of labeling problem has been one of new fields of graph theory.In this thesis, we will discuss one kind of vertex-labeling problems: circular labeling. Given 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), the distance of u and v, is the length of a shortest path between u and v. 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 λ_2,1(G), is the minimum k such that G has a k - L(2, 1)-labeling. Circular labeling is a variation of the L(2, 1)-labeling,and it is a function f: V(G)→{0,1,2, ··· , k-1} such that:where |x|_k := min{|x|, k -|x|}. A k-circular labeling is a circular labeling such that no label is greater than k -1. The circular labeling number,denoted by σ(G),is the minimum k such that G has a circular labeling.Here is the main results of this thesis:1. Circular labeling number of Cartesian product of paths;2. Circular labeling number of Cartesian product of a path and a cycle;3. Circular labeling number of Cartesian product of cycles;4. Circular labeling number of Direct product,Strong product of paths;5. Circular labeling number of wheel graph,r-path graph and Mycielski graph.