Study On The Problem Of L(p, Q)-Labeling Of Graphs

The L(p,q)-labeling of graphs arises from a variation frequency assignment problem by Hale. Given a graph G and two positive integers p ≥ q, an m-L(p, q)-labeling of G is a function f : V(G) → {0,1,2, ..., m} such that, for any two vertices x,y ∈ V(G),|f(x) - f(y)| ≥ p if dG(x,y) = 1; and |f(x) - f(y)| ≥ q if dG(x,y) = 2. The L(p,q)- number of G, denoted by λp,q(G), is the smallest number m such that G has an m - L(p,q)- labeling.In this thesis, we firstly summarize the main results and evolution on the L(p,q)-labeling in recent years, then we will investigate the L(1,1)-labeling and the L(2,1)-labeling of the line graph L(G) of a simple graph G with maximum degree △(G) ≤ 4. We usually denoted by λ'p,q(G) the L(p,q)-labeling number of L(G). Finally, we explore the L(p,q)-labeling problem of some classes of graphs.The L(1,1)-labeling of L(G) is analogous to the strong edge coloring of graph G. We denoted the strong edge chromatic index(the list strong edge chromatic index) of G by SX'(G)(SX'l(G)), then SX'(G) = λ'1,1(G) + 1. In 1985, Erdos and Nesetril conjectured that for any simple graph G, SX'(G) ≤ 5△2(G)/4 when △(G) is even and SX'(G) ≤ 5△2(G)/4 - △(G)/2 + 1/4 when △(G) is odd. For △(G) = 4, the conjectured bound is 20, previously, Horak proved SX'(G) ≤ 23. For △(G) = 3, the conjectured bound is 10, this bound has been proved by Anderson, and independently, Horak et al.In this thesis, we show that SX'l(G) ≤ 22 when △(G) = 4. Furthermore, if the girth g(G) ≤ 4, then SX'(G) ≤ 21. Since SX'(G) ≤ SX'l(G), so we improved the result of Horak. Also, we proved that if △(G) = 3, then SX'l(G) ≤ 11 .For graph G with △(G) ≤ 4, Georges and Mauro proved λ'2,1(G) ≤ 2(△(G) -1)(△(G) + 2). We improved this bound to that λ'2,1(G) ≤ 2△2(G) - 2.Finally, we explore the L(p,q)-labeling of k-degenerated and M-matched sum G1M+G2 of G1 and G2. In particular, we present the attainable lower and the upper bounds for cactus and unicycle.