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

Abstract

▫$\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.

Keywords

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;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM PEF - Faculty of Education
UDC: 519.17
COBISS: 13843801 Link will open in a new window
ISSN: 1027-5487
Views: 64
Downloads: 30
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Slovenian
Secondary title: Kode in L(2,1)-označitve grafov Sierpińskega
Secondary abstract: 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.
Secondary keywords: Teorija grafov;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 671-681
Volume: ǂVol. ǂ9
Issue: ǂno. ǂ4
Chronology: 2005
DOI: 10.11650/twjm/1500407890
ID: 1472591