Improved upper bounds on the L(2,1) -labeling of the skew and converse skew product graphs

Zhendong Shao, Dapeng Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 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) ≤ Δ2 for any simple graph with maximum degree Δ ≥ 2. This paper considers the graph formed by the skew product and the converse skew product of two graphs with a new approach on the analysis of adjacency matrices of the graphs as in [W.C. Shiu, Z. Shao, K.K. Poon, D. Zhang, A new approach to the L (2, 1)-labeling of some products of graphs, IEEE Trans. Circuits Syst. II: Express Briefs (to appear)] and improves the previous upper bounds significantly.
Original languageEnglish
Pages (from-to)230-233
Number of pages4
JournalTheoretical Computer Science
Volume400
Issue number1-3
DOIs
Publication statusPublished - 9 Jun 2008

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this