Radio numbers for generalized prism graphs

• Autorzy: Paul Martinez , Juan Ortiz , Maggy Tomova , Cindy Wyels
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

radio number   radio labeling   prism graphs  

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C78: Graph labelling (graceful graphs, bandwidth, etc.)

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2011
• Tom: 31
• Numer: 1
• Strony: 45-62

Daty

wydano

2011

otrzymano

2009-04-01

poprawiono

2010-04-01

zaakceptowano

2010-04-06

Twórcy

autor

Paul Martinez

• California State University Channel Islands

autor

Juan Ortiz

• Lehigh University

autor

Maggy Tomova

• The University of Iowa

autor

Cindy Wyels

• California State University Channel Islands

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1529