Try new release: COBISS+
 Shared database: COBIB.SI - Union bibliographic/catalogue database (No. of records: 5.062.846)

Selected record permalink

AuthorKlavžar, Sandi
Milutinović, Uroš
Petr, Ciril
Title 1-perfect codes in Sierpiński graphs / Sandi Klavžar, Uroš Milutinović, Ciril Petr
Other titles1-popolne kode v grafih Sierpińskega
Type/contenttype of material article - component part
LanguageEnglish
Publication date2001
Physical descriptionstr. 1-18
NotesBibliografija: str. 17-18
Uncontrolled subject headingsmatematika / teorija grafov / 1-popolne kode / grafi hanojskih stolpov / grafi Sierpińskega / dominantno število grafa / mathematics / graph theory / 1-perfect codes / Tower of Hanoi graphs / Sierpiński graphs / domination number of graphs
UDC519.17:004
Other class numbers
94B25
05C69
68R15
11A07 (MSC 2000)
SummaryGrafi Sierpińskega $S(n,k)$ predstavljajo posplošitev grafov hanojskih stolpov - graf $S(n,3)$ je izomorfen grafu $H_n$ hanojskih stolpov z $n$ obroči. Dokazano je, da grafi $S(n,k)$ vsebujejo enolične 1-popolne kode. S tem je razširjen prej znani rezultat za $H_n$. Predstavljen je tudi učinkovit algoritem dekodiranja. Predlagani pristop je bistveno različen od znanega pristopa za grafe $H_n$.
Sierpiński graphs $S(n,k)$ generalize the Tower of Hanoi graphs - the graph $S(n,3)$ is isomorphic to the graph $H_n$ of the Tower of Hanoi with $n$ disks. A 1-perfect code (or an efficient dominating set) in a graph $G$ is a vertex subset of $G$ with the property that the closed neighborhoods of its elements form a partition of $V(G)$. It is proved that the graphs $S(n,k)$ possess unique 1-perfect codes, thus extending a previously known result for $H_n$. An efficient decoding algorithm is also presented. The present approach, in particular the proposed (de)coding, is intrinsically different from the approach to $H_n$.
COBISS.SI-ID11285337
See publication: TI=Preprint series ISSN: 1318-4865.- Vol. 39, št. 794 (2001), str. 1-18