L(2,1)-Edge-Labelings of the Edge-Path-Replacement of a Graph

Two edges e(1) and e(2) in a graph G are said to be adjacent if they have a vertex in common, and distance two apart if they are nonadjacent but both are adjacent to a common edge. An L(2, 1)-edge-labeling of a graph G is an assignment of nonnegative integers, called labels, to the edges of G such that the difference between labels of any two adjacent edges is at least 2, and the labels of any two edges that are distance two apart are different. The span of an L(2, 1)-edge-labeling of a graph G is the difference between the maximum and minimum labels. The minimum span over all L(2, 1)-edge-labelings of a graph G is called the L(2, 1)-edge-labeling number of G, denoted by lambda'(G). For k >= 3, the edge-path-replacement of a graph G, denoted by G(P-k), is a graph obtained by replacing each edge of G with a path P-k on k vertices. This paper investigates the L(2, 1)-edge-labeling number of the edge-path-replacement G(P-k) of a graph G for k >= 3. We get the following main results: (1) Let G be a graph with maximum degree Delta >= 4 and k be an integer not less than 4, then 2 Delta - 2 <= lambda(G(P-4)) <= 2 Delta if Delta is odd, and otherwise lambda'(G(P-k)) = 2 Delta - 2. (2) Let G be a graph with maximum degree Delta. Then 2 Delta - 2 <= lambda'(G(P-3)) <= 3 Delta - 2 when Delta is even, and 2 Delta - 2 <= lambda'(G(P-3)) <= 3 Delta+ 1 when Delta is odd.