Czasopismo
Tytuł artykułu
Treść / Zawartość
Pełne teksty:
Warianty tytułu
Języki publikacji
Abstrakty
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
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
45-62
Opis fizyczny
Daty
wydano
2011
otrzymano
2009-04-01
poprawiono
2010-04-01
zaakceptowano
2010-04-06
Twórcy
autor
- California State University Channel Islands
autor
- Lehigh University
autor
- The University of Iowa
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1529