Iskanje po katalogu digitalne knjižnice

Opis: Za dani graf ▫$G$▫ in celi števili ▫$a$▫ in ▫$b$▫ je ▫$(a,b)$▫-koda grafa ▫$G$▫ množica vozlišč ▫$C$▫, tako da ima vsako vozlišče iz ▫$C$▫ natanko ▫$a$▫ sosedov v ▫$C$▫, vsako drugo vozlišče pa natanko ▫$b$▫ sosedov v ▫$C$▫. V tem prispevku klasificiramo števila ▫$a$▫ in ▫$b$▫, za katera obstajajo ▫$(a,b)$▫-kode v grafih Sierpińskega.
Ključne besede: graph theory, codes in graphs, perfect codes, Sierpiński graphs
Objavljeno v DKUM: 10.07.2017; Ogledov: 1166; Prenosov: 178
Celotno besedilo (786,68 KB)
Gradivo ima več datotek! Več...

Opis: 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.
Ključne besede: matematika, teorija grafov, ▫$L(2,1)$▫-označitev, ▫$lambda$▫-število, grafovske kode, popolne kode, grafi Sierpińskega, mathematics, graph theory, ▫$L(2,1)▫$-labelings, ▫$lambda$▫-number, codes in graphs, perfect codes, Sierpiński graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 1224; Prenosov: 71
Povezava na celotno besedilo