L(j,k)-Labelings and L(j, k)-Edge-Labelingsof Graphs

摘要

Let j and k be two positive integers. An L(j, k)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j, k)-labelings of a graph G is called the λ_(j,k)-number of G, denoted by λ_(j,k)(G). Similarly, we can define L(j, k)-edge-labeling and L(j, k)-edge-labeling number, λ_(j,k)(G), of a graph G. In this pa-per, we show that if G is K_(1,3)-free with maximum degree Δ then λ_(j,k)(G) ≤ k[Δ~2/2.] jΔ - 1 except that G is a 5-cycle and j = k. Consequently we obtain an upper bound for λ_(j,k)(G) in terms of the maximum degree of L(G), where L(G) is the line graph of G. This improves the upper bounds for λ_(2,1)(G) and λ_(1,1)(G) given by Georges and Mauro [Ars Combinatoria 70 (2004), 109-128]. As a corollary we show that Griggs and Yeh' conjecture that λ_(2,1) (G) ≤ Δ~2 holds for all K_(1,3)-free graphs and hence holds for all line graphs. We also investigate the upper bound for λ_(j,k) (G) for K_(1,3)-free graphs G.