TY - JOUR

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

AU - Shao, Zhendong

AU - Klavžar, Sandi

AU - SHIU, Wai Chee

AU - Zhang, David

N1 - Funding Information:
Manuscript received July 16, 2007; revised October 6, 2007. First published April 1, 2008; last published July 16, 2008 (projected). This work was supported in part by the Ministry of Science of Slovenia under Grant P1-0297, by CERG, by the Research Grants Council of Hong Kong, by FRG, by the Hong Kong Baptist University, by the UGC/CRC fund from the HKSAR Government, by the central fund from the Hong Kong Polytechnic University, and by the National Science Foundation of China and the 863 funds under Contract 60620160097 and Contract 2006AA01Z193. This paper was recommended by Associate Editor S. Tsukiyama.

PY - 2008/7

Y1 - 2008/7

N2 - 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.

AB - 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.

KW - Channel assignment

KW - Graph direct product

KW - Graph strong product

KW - L(2, 1) -labeling

UR - http://www.scopus.com/inward/record.url?scp=48849107345&partnerID=8YFLogxK

U2 - 10.1109/TCSII.2008.921411

DO - 10.1109/TCSII.2008.921411

M3 - Article

AN - SCOPUS:48849107345

VL - 55

SP - 685

EP - 689

JO - IEEE Transactions on Circuits and Systems II: Express Briefs

JF - IEEE Transactions on Circuits and Systems II: Express Briefs

SN - 1549-7747

IS - 7

ER -