20.500.12556/DKUM-51513 Codes and L(2,1)-labelings in Sierpiński graphs Kode in L(2,1)-označitve grafov Sierpińskega 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. ▫$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. 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 true true false Angleški jezik Slovenski jezik Članek v reviji 2015-07-10 14:52:48 2015-07-10 14:52:48 2024-03-08 10:31:22 2019-07-11 07:21:03 2005 0 0 str. 671-681 no. 4 Vol. 9 2005 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 13412872 13843801 1027-5487 URN:SI:UM:DK:NCRIDAUC http://www.math.nthu.edu.tw/~tjm/myweb/FrameConAbs.htm 1 https://dk.um.si/Dokument.php?lang=slv&id=76073 Pedagoška fakulteta 0 0 0