Improved bounds on the L(2,1)-number of direct and strong products of graphs

Zhendong Shao*, Sandi Klavžar, Wai Chee SHIU, David Zhang

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

16 Citations (Scopus)


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. This paper considers the graph formed by the direct product and the strong product of two graphs and gets better bounds than those of Klavžar and Špacapan with refined approaches.

Original languageEnglish
Pages (from-to)685-689
Number of pages5
JournalIEEE Transactions on Circuits and Systems II: Express Briefs
Issue number7
Publication statusPublished - Jul 2008

Scopus Subject Areas

  • Electrical and Electronic Engineering

User-Defined Keywords

  • Channel assignment
  • Graph direct product
  • Graph strong product
  • L(2, 1) -labeling


Dive into the research topics of 'Improved bounds on the L(2,1)-number of direct and strong products of graphs'. Together they form a unique fingerprint.

Cite this