標題: On L(d, 1)-labelings of graphs
作者: Chang, GJ
Ke, WT
Kuo, D
Liu, DDF
Yeh, 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:

  1. 000087401100005.pdf