Radio numbers for generalized prism graphs

Paul Martinez; Juan Ortiz; Maggy Tomova; Cindy Wyels

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 1, page 45-62
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Paul Martinez, et al. "Radio numbers for generalized prism graphs." Discussiones Mathematicae Graph Theory 31.1 (2011): 45-62. <http://eudml.org/doc/270953>.

@article{PaulMartinez2011,
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.},
author = {Paul Martinez, Juan Ortiz, Maggy Tomova, Cindy Wyels},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {radio number; radio labeling; prism graphs},
language = {eng},
number = {1},
pages = {45-62},
title = {Radio numbers for generalized prism graphs},
url = {http://eudml.org/doc/270953},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Paul Martinez
AU - Juan Ortiz
AU - Maggy Tomova
AU - Cindy Wyels
TI - Radio numbers for generalized prism graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 1
SP - 45
EP - 62
AB - 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.
LA - eng
KW - radio number; radio labeling; prism graphs
UR - http://eudml.org/doc/270953
ER -

References

top
  1. [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. Zbl0860.05064
  2. [2] G. Chartrand, D. Erwin, P. Zhang and F. Harary, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001) 77-85. Zbl0989.05102
  3. [3] G. Chartrand and P. Zhang, Radio colorings of graphs-a survey, Int. J. Comput. Appl. Math. 2 (2007) 237-252. 
  4. [4] W.K. Hale, Frequency assignment: theory and application, Proc. IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899. 
  5. [5] R. Khennoufa and O. Togni, The Radio Antipodal and Radio Numbers of the Hypercube, Ars Combin., in press. Zbl1265.05536
  6. [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. Zbl1216.05134
  7. [7] D.D.-F. Liu, Radio number for trees, Discrete Math. 308 (2008) 1153-1164, doi: 10.1016/j.disc.2007.03.066. Zbl1133.05090
  8. [8] D.D.-F. Liu and M. Xie, Radio numbers of squares of cycles, Congr. Numer. 169 (2004) 101-125. Zbl1064.05089
  9. [9] D.D.-F. Liu and M. Xie, Radio number for square paths, Ars Combin. 90 (2009) 307-319. Zbl1224.05451
  10. [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. Zbl1095.05033
  11. [11] P. Zhang, Radio labelings of cycles, Ars Combin. 65 (2002) 21-32. Zbl1071.05573

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.