The L(2, 1)-labeling problem on ditrees

Gerard J. Chang, Sheng Chyang Liaw

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

An L(2, 1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x) - f(y)| ≥ 2 if d G(x, y) = 1 and |f(x) - f(y)| ≥ 1 if dG(x, y) = 2. The L(2, 1)-labeling problem is to find the smallest number λ(G) such that there exists a L(2, 1)-labeling function with no label greater than λ(G). Motivated by the channel assignment problem introduced by Hale, the L(2, 1)-labeling problem has been extensively studied in the past decade. In this paper, we study this concept for digraphs. In particular, results on ditrees are given.

Original languageEnglish
Pages (from-to)23-31
Number of pages9
JournalArs Combinatoria
Volume66
StatePublished - Jan 2003

Keywords

  • Ditree
  • L(2, 1)-labeling number
  • L(2, l)-labeling

Fingerprint

Dive into the research topics of 'The L(2, 1)-labeling problem on ditrees'. Together they form a unique fingerprint.

Cite this