PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2011 | 31 | 1 | 45-62
Tytuł artykułu

Radio numbers for generalized prism graphs

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
31
Numer
1
Strony
45-62
Opis fizyczny
Daty
wydano
2011
otrzymano
2009-04-01
poprawiono
2010-04-01
zaakceptowano
2010-04-06
Twórcy
  • 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
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.