Full metadata record
DC FieldValueLanguage
dc.contributor.authorChang, GJen_US
dc.contributor.authorKe, WTen_US
dc.contributor.authorKuo, Den_US
dc.contributor.authorLiu, DDFen_US
dc.contributor.authorYeh, RKen_US
dc.date.accessioned2014-12-08T15:45:12Z-
dc.date.available2014-12-08T15:45:12Z-
dc.date.issued2000-06-06en_US
dc.identifier.issn0012-365Xen_US
dc.identifier.urihttp://hdl.handle.net/11536/30465-
dc.description.abstractGiven 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.en_US
dc.language.isoen_USen_US
dc.subjectvertex-coloringen_US
dc.subjectdistance two labelingen_US
dc.subjectchannel assignment problemen_US
dc.subjectL(2,1)-labelingen_US
dc.titleOn L(d, 1)-labelings of graphsen_US
dc.typeArticleen_US
dc.identifier.journalDISCRETE MATHEMATICSen_US
dc.citation.volume220en_US
dc.citation.issue1-3en_US
dc.citation.spage57en_US
dc.citation.epage66en_US
dc.contributor.department應用數學系zh_TW
dc.contributor.departmentDepartment of Applied Mathematicsen_US
dc.identifier.wosnumberWOS:000087401100005-
dc.citation.woscount97-
Appears in Collections:Articles


Files in This Item:

  1. 000087401100005.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.