The L (2, 1)-labeling on the skew and converse skew products of graphs

Zhendong Shao, Roger K. Yeh, Dapeng Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 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. This work considers the graph formed by the skew product and the converse skew product of two graphs. As corollaries, the new graph satisfies the above conjecture (with minor exceptions).
Original languageEnglish
Pages (from-to)59-64
Number of pages6
JournalApplied Mathematics Letters
Volume20
Issue number1
DOIs
Publication statusPublished - 1 Jan 2007

Keywords

  • Channel assignment
  • Graph converse skew product
  • Graph skew product
  • L (2, 1)-labeling

ASJC Scopus subject areas

  • Applied Mathematics

Cite this