A new approach to the L(2,1)-labeling of some products of graphs

Wai Chee SHIU, Zhendong SHAO, Kin Keung Eric POON, David ZHANG

Research output: Contribution to journalArticles

8 Citations (Scopus)

Abstract

The frequency assignment problem is to assign a frequency which is a nonnegative integer to each radio transmitter so that interfering transmitters are assigned frequencies whose separation is not in a set of disallowed separations. This frequency assignment problem can be modelled with vertex labelings of graphs. 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. In this paper, we develop a dramatically new approach on the analysis of the adjacency matrices of the graphs to estimate the upper bounds of λ-numbers of the four standard graph products. By the new approach, we can achieve more accurate results and with significant improvement of the previous bounds. Copyright © 2008 IEEE Circuits and Systems Society.
Original languageEnglish
Pages (from-to)802-805
JournalIEEE transactions on circuits and systems. II, Express briefs
Volume55
Issue number8
DOIs
Publication statusPublished - Aug 2008

Citation

Shiu, W. C., Shao, Z., Poon, K. K. & Zhang, D. (2008). A new approach to the L(2,1)-labeling of some products of graphs. IEEE transactions on circuits and systems. II, Express briefs, 55(8), 802-805.

Keywords

  • Strong product
  • Direct product
  • Lexicographic product
  • Cartesian product
  • L(2,1)-labeling
  • Channel assignment

Fingerprint Dive into the research topics of 'A new approach to the L(2,1)-labeling of some products of graphs'. Together they form a unique fingerprint.