The L (2, 1)-labeling on graphs and the frequency assignment problem

Zhendong Shao, Roger K. Yeh, Dapeng Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)

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 (x, y) = 1 and | f (x) - f (y) | ≥ 1 if d (x, y) = 2, where d (x, y) denotes the distance between x and y in G. The L (2, 1)-labeling number λ (G) of G is the smallest number k such that G has an L (2, 1)-labeling with max {f (v) : v ∈ V (G)} = k. Griggs and Yeh conjecture that λ (G) ≤ Δ2for any simple graph with maximum degree Δ ≥ 2. In this work, we consider the total graph and derive its upper bound of λ (G). The total graph plays an important role in other graph coloring problems. Griggs and Yeh's conjecture is true for the total graph in some cases.
Original languageEnglish
Pages (from-to)37-41
Number of pages5
JournalApplied Mathematics Letters
Volume21
Issue number1
DOIs
Publication statusPublished - 1 Jan 2008

Keywords

  • Channel assignment
  • L (2, 1)-labeling
  • Total graph

ASJC Scopus subject areas

  • Applied Mathematics

Cite this