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

Zhendong Shao, Sandi Klavžar, Wai Chee Shiu, Dapeng Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 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. 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
Volume55
Issue number7
DOIs
Publication statusPublished - 1 Jul 2008

Keywords

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

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this