1. Perfect codes in direct products of cycles - a complete characterizationJanez Žerovnik, 2008, original scientific article Abstract: Let ▫$G = times^n_{i=1}C_{ell_i}$▫ be a direct product of cycles. It is known that for any ▫$r le 1$▫, and any ▫$n le 2▫$, each connected component of ▫$G$▫ contains a so-called canonical ▫$r$▫-perfect code provided that each ▫$ell_i$▫ is a multiple of ▫$r^n + (r+1)^n$▫. Here we prove that up to a reasonably defined equivalence, these are the only perfect codes that exist.
Keywords: matematika, teorija grafov, korekcijske kode, direktni produkt grafov, popolne kode, cikli, mathematics, graph theory, error-correcting codes, direct product of graphs, perfect codes, cycles
Published in DKUM: 10.07.2015; Views: 1886; Downloads: 92
 Link to full text |
2. Nonexistence of face-to face four-dimensional tilings in the Lee metricSimon Špacapan, 2007, original scientific article Abstract: A family of ▫$n$▫-dimensional Lee spheres ▫$mathcal{L}$▫ is a tiling of ▫${mathbb{R}}^n$▫ if ▫$cupmathcal{L} = {mathbb{R}}^n$▫ and for every ▫$L_u, L_v in mathcal{L}$▫, the intersection ▫$L_u cap L_v$▫ is contained in the boundary of ▫$L_u$▫. If neighboring Lee spheres meet along entire ▫$(n-1)$▫-dimensional faces, then ▫$mathcal{L}$▫ is called a face-to-face tiling. We prove nonexistence of a face-to-face tiling of ▫${mathbb{R}}^4$▫, with Lee spheres of different radii.
Keywords: delitev, Leejeva metrika, popolne kode, tiling, Lee metric, perfect codes
Published in DKUM: 10.07.2015; Views: 1003; Downloads: 84
Link to full text |
3. An almost complete description of perfect codes in direct products of cyclesSandi Klavžar, Simon Špacapan, Janez Žerovnik, 2006, original scientific article Abstract: Naj bo ▫$G = times_{i=1}^nC_{ell_i}$▫ direktni produkt ciklov. Dokazano je, da za vsak ▫$r ge 1$▫ in za vsak ▫$n ge 2$▫ velja naslednje. Če je vsak ▫$ell_i$▫ večkratnik od ▫$r^n + (r+1)^n$▫, tedaj vsaka povezana komponenta grafa ▫$G$▫ vsebuje ▫$r$▫-popolno kodo. Po drugi strani je tudi dokazano, da če koda grafa ▫$G$▫ vsebuje izbrano točko in njene lokalno kanonične točke, tedaj je vsak ▫$ell_i$▫ večkratnik od ▫$r^n + (r+1)^n$▫. Nadalje je dokazano, da je ▫$r$▫-popolna koda ▫$(r ge 2)$▫ grafa ▫$G$▫ enolično določena z ▫$n$▫ točkami. Postavljena je domneva, da za ▫$r ge 2$▫ ne obstajajo nobene druge kode v $G$ razen tistih, ki so konstruirane v članku.
Keywords: matematika, teorija grafov, korekcijske kode, direktni produkt grafov, popolne kode, cikli, mathematics, graph theory, error-correcting codes, direct product of graphs, perfect codes, cycles
Published in DKUM: 10.07.2015; Views: 24186; Downloads: 101
Link to full text |
4. Codes and L(2,1)-labelings in Sierpiński graphsSylvain Gravier, Sandi Klavžar, Michel Mollard, 2005, original scientific article 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.
Keywords: 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
Published in DKUM: 10.07.2015; Views: 1224; Downloads: 71
Link to full text |
