Some Labeling Problems Of Graphs

The labeling problems of graphs considered in this doctoral dissertation has originated from distance two labeling problem, which are of significant applica-tions in Frequency Assignment problem. A k-L(p,q)-labeling of a graph G is a mapping from V(G) to{0,1,..., k} such that adjacent vertices receive numbers differed by at least p and vertices at distance 2 receive numbers differed by at least q. A k-(d, 1)-total labeling of a graph G is a mapping from V(G) U E(G) to {0,1,..., k} such that adjacent vertices or adjacent edges receive different num-bers, and the vertex and the edge which are incident receive numbers differed by at least d. A (2,1)-coupled labeling of a plane graph G is a mapping from V(G) ∪F(G) to{0,f,..., k} such that adjacent vertices or adjacent faces receive different numbers, and the vertex and the face which are incident receive numbers differed by at least 2.The dissertation focuses on studying the above labeling problems and con-sists of the following four chapters.In Chapter 1, we collect some notations and terms, give a chief survey on these labeling problems, and state the main results of this dissertation.In Chapter 2, we characterize completely the L(2,1)-labeling number of all trees T with maximum degree 3. Firstly, we establish an useful structural lemma on T. Then, by introducing a labeling procedure, we define good trees with particular structures. Finally, we prove that a tree T with △=3 has the L(2,1)-labeling number 4 if and only if T is good.In Chapter 3, we investigate the (2,1)-total labeling of graphs. Two sufficient onditions for a tree T to be Type 1 are established:(I) For a tree T with △≥4, if every major vertex is adjacent to at most △-3 major vertices in T, then T is of type 1; (Ⅱ) For a tree T with △≥9, if there are no two bad vertices at even distance, then T is of type 1. Moreover, we show that the (2, 1)-total labeling number of an outerplanar graph is at most △+2.In Chapter 4, we introduce the new concept of (2,1)-coupled labeling of plane graphs, and give tight upper bounds of (2,1)-coupled labeling number for trees, cycles, K4, Eulerian bipartite graphs, outerplanar graphs, etc. In addition, we completely characterize outerplane graphs having at most one closed inner face according to their (2,1)-coupled labeling numbers.