PDF

Discussiones Mathematicae Graph Theory 31(1) (2011) 45-62
DOI: https://doi.org/10.7151/dmgt.1529

RADIO NUMBERS FOR GENERALIZED PRISM GRAPHS

Paul Martinez California State University Channel Islands e-mail: paul.martinez@csuci.edu

Juan Ortiz Lehigh University e-mail: jpo208@lehigh.edu

Maggy Tomova The University of Iowa e-mail: mtomova@math.uiowa.edu

Cindy Wyels California State University Channel Islands e-mail: cynthia.wyels@csuci.edu

Abstract

A radio labeling is an assignment c:V(G)→ N such that every distinct pair of vertices u,v satisfies the inequality d(u,v)+|c(u)−c(v)| ≥ diam(G)+1. The span of a radio labeling is the maximum value. The radio number of G, rn(G), is the minimum span over all radio labelings of G. Generalized prism graphs, denoted Z_n,s, s ≥ 1, n ≥ s, have vertex set {(i,j) | i = 1,2 and j = 1,...,n} and edge set {((i,j),(i,j ±1))} ∪{((1,i),(2,i+σ)) | σ = −⌊(s−1)/2⌋ …,0,…,⌊s/2⌋}. In this paper we determine the radio number of Z_n,s for s = 1,2 and 3. In the process we develop techniques that are likely to be of use in determining radio numbers of other families of graphs.

Keywords: radio number, radio labeling, prism graphs.

2010 Mathematics Subject Classification: 05C78, 05C15.

References

[1]	G. Chang and D. Kuo, The L(2,1)-labeling problem on graphs, SIAM J. Discrete Math. 9 (1996) 309-316, doi: 10.1137/S0895480193245339.
[2]	G. Chartrand, D. Erwin, P. Zhang and F. Harary, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001) 77-85.
[3]	G. Chartrand and P. Zhang, Radio colorings of graphs-a survey, Int. J. Comput. Appl. Math. 2 (2007) 237-252.
[4]	W.K. Hale, Frequency assignment: theory and application, Proc. IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899.
[5]	R. Khennoufa and O. Togni, The Radio Antipodal and Radio Numbers of the Hypercube, Ars Combin., in press.
[6]	X. Li, V. Mak and S. Zhou, Optimal radio labellings of complete m-ary trees, Discrete Appl. Math. 158 (2010) 507-515, doi: 10.1016/j.dam.2009.11.014.
[7]	D.D.-F. Liu, Radio number for trees, Discrete Math. 308 (2008) 1153-1164, doi: 10.1016/j.disc.2007.03.066.
[8]	D.D.-F. Liu and M. Xie, Radio numbers of squares of cycles, Congr. Numer. 169 (2004) 101-125.
[9]	D.D.-F. Liu and M. Xie, Radio number for square paths, Ars Combin. 90 (2009) 307-319.
[10]	D.D.-F. Liu and X. Zhu, Multilevel distance labelings for paths and cycles, SIAM J. Discrete Math. 19 (2009) 610-621 (electronic), doi: 10.1137/S0895480102417768.
[11]	P. Zhang, Radio labelings of cycles, Ars Combin. 65 (2002) 21-32.

Received 1 April 2009
Revised 1 April 2010
Accepted 6 April 2010