Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

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ść

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

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.

Identyfikatory

Identyfikator YADDA

bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1529