標題: On L(d, 1)-labelings of graphs 作者: Chang, GJKe, WTKuo, DLiu, DDFYeh, RK應用數學系Department of Applied Mathematics 關鍵字: vertex-coloring;distance two labeling;channel assignment problem;L(2,1)-labeling 公開日期: 6-Jun-2000 摘要: Given a graph G and a positive integer d, an L(d, 1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and u are adjacent, then f(u) - f(v) greater than or equal to d; if u and v are not adjacent but there is a two-edge path between them, then f(u)- f(v) greater than or equal to 1. The L(d, 1)-number of G, lambda(d)(G), is defined as the minimum m such that there is an L(d, 1)-labeling f of G with f(V) subset of or equal to {0, 1, 2,,.., m}. Motivated by the channel assignment problem introduced by Hale (Proc, IEEE 68 (1980) 1497-1514), the L(2, 1)-labeling and the L(1, 1)-labeling (as d = 2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that lambda(d)(G) less than or equal to Delta(2) + (d - 1)Delta for any graph G with maximum degree d. Different lower and upper bounds of lambda(d)(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs. (C) 2000 Elsevier Science B,V. All rights reserved. URI: http://hdl.handle.net/11536/30465 ISSN: 0012-365X 期刊: DISCRETE MATHEMATICS Volume: 220 Issue: 1-3 起始頁: 57 結束頁: 66 Appears in Collections: Articles

Files in This Item: