Sylvain Gravier (Avtor), Sandi Klavžar (Avtor), Michel Mollard (Avtor)

Povzetek

▫$\lambda$▫-število grafa ▫$G$▫ je minimalna vrednost ▫$\lambda$▫, za katero graf ▫$G$▫ dopušča označitev z oznakami iz množice ▫$\{0, 1,..., \lambda\}$▫, ter pri tem točki na razdalji dva dobita različni oznaki, sosednji točki pa prejmeta oznaki, ki se razlikujeta vsaj za dva. Sierpińskijevi grafi ▫$S(n,k)$▫ predstavljajo posplošitev grafov Hanojskega stolpa - graf ▫$S(n,3)$▫ je izomorfen grafu Hanojskega stolpa z ▫$n$▫ diski. Dokazano je, da za vsak ▫$n \ge 2$▫ in za vsak ▫$k \ge 3$▫ velja ▫$\lambda (S(n,k)) = 2k$▫. Za dosego tega rezultata so v podrobnosti študirane (popolne) kode v grafih Sierpińskega. Med drugim je narejen nov dokaz njihove enoličnosti.

Ključne besede

matematika;teorija grafov;▫$L(2,1)$▫-označitev;▫$\lambda$▫-število;grafovske kode;popolne kode;grafi Sierpińskega;ne zaključna dela;mathematics;graph theory;▫$L(2,1)▫$-labelings;▫$\lambda$▫-number;codes in graphs;perfect codes;Sierpiński graphs;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM PEF - Pedagoška fakulteta
UDK: 519.17
COBISS: 13843801 Povezava se bo odprla v novem oknu
ISSN: 1027-5487
Št. ogledov: 64
Št. prenosov: 30
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: Kode in L(2,1)-označitve grafov Sierpińskega
Sekundarni povzetek: The ▫$\lambda$▫-number of a graph ▫$G$▫ is the minimum value ▫$\lambda$▫ such that ▫$G$▫ admits a labeling with labels from ▫$\{0, 1,..., \lambda\}$▫ where vertices at distance two get different labels and adjacent vertices get labels that are at least two apart. Sierpiński graphs ▫$S(n,k)$▫ generalize the Tower of Hanoi graphs - the graph ▫$S(n,3)$▫ is isomorphic to the graph of the Tower of Hanoi with ▫$n$▫ disks. It is proved that for any ▫$n \ge $▫2 and any ▫$k \ge 3$▫, ▫$\lambda (S(n,k)) = 2k$▫. To obtain the result (perfect) codes in Sierpiński graphs are studied in detail. In particular a new proof of their (essential) uniqueness is obtained.
Sekundarne ključne besede: Teorija grafov;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 671-681
Letnik: ǂVol. ǂ9
Zvezek: ǂno. ǂ4
Čas izdaje: 2005
DOI: 10.11650/twjm/1500407890
ID: 1472591