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

Selected record permalink

AuthorHinz, Andreas M., 1954-
Klavžar, Sandi
Milutinović, Uroš
Parisse, Daniele
Petr, Ciril
Title Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence / Andreas M. Hinz ... [et al.]
Other titlesMetrične lastnosti grafov hanojskih stolpov in Sternovo diatomično zaporedje
Type/contenttype of material article - component part
LanguageEnglish
Publication date2005
Physical descriptionstr. 693-708
NotesSoavtorji: Sandi Klavžar, Uroš Milutinović, Daniele Parisse, Ciril Petr
Bibliografija: str. 707-708
Uncontrolled subject headingsmatematika / hanojski stolpi / najkrajša pot / Sternovo diatomično zaporedje / ravninske vložitve / mathematics / Tower of Hanoi / shortest path / Stern's diatomic sequence / plane embedding
UDC519.1
Other class numbers
05A15
05C12
11B83
51M15 (MSC 2000)
URLhttp://www.sciencedirect.com/science/journal/01956698
SummaryZnano je, da v grafih hanojskih stolpov obstajata kvečjemu dve najkrajši poti med dvema danima točkama grafa. Podana je formula, ki za dane točke $v$ prešteje število točk $u$, tako da obstajata dve najkrajši $u,v$-poti. Formula je izražena s pomočjo Sternovega diatoničnega zaporedja $b(n)$, $n \ge 0$. Iz formule sledi, da je število enako 0 samo za točke stopnje 2. Predstavljene so tudi ravninske vložitve grafov hanojskih stolpov, ki omogočajo ekspliciten opis $b(n)$ kot število elementov v množici točk hanojskih stolpov, ki so presekane z določenimi premicami v ravnini.
It is known that in the Tower of Hanoi graphs there are at most two different shortest paths between any fixed pair of vertices. A formula is given that counts, for a given vertex $v$, the number of vertices $u$ such that there are two shortest $u,v$-paths. The formula is expressed in terms of Stern's diatomic sequence $b(n)$ $(n \ge 0)$ and implies that only for vertices of degree two this number is zero. Plane embeddings of the Tower of Hanoi graphs are also presented that provide an explicit description of $b(n)$ as the number of elements of the sets of vertices of the Tower of Hanoi graphs intersected by certain lines in the plane.
COBISS.SI-ID13417305
See publication: TI=European journal of combinatorics = Journal européen de combinatoire = Europäische Zeitschrift für Kombinatorik ISSN: 0195-6698.- Vol. 26, no. 5 (2005), str. 693-708

info Electronic version of document accessible or this is electronic resource