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 · IEEE Transactions on Circuits & Systems II Express Briefs · 2008
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. AnL(2,1)-labeling of a graphGis a functionffrom the vertex setV(G) to the set of all nonnegative integers such that |f(x)-f(y)| ges 2 ifd(x,y)=1 and |f(x)-f(y)| ges 1 ifd(x,y)=2 , whered(x,y) denotes the distance betweenxandyinG. TheL(2,1) -labeling number lambda(G) ofGis the smallest numberksuch thatGhas anL(2,1)-labeling with max{f(v):visinV(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 Klavzar and Spacapan with refined approaches.