Sandi Klavžar (Author), Simon Špacapan (Author), Janez Žerovnik (Author)

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;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FS - Faculty of Mechanical Engineering
UDC: 519.17
COBISS: 14026329 Link will open in a new window
ISSN: 0196-8858
Views: 23650
Downloads: 84
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: Unknown
Secondary title: Skoraj celotni opis popolnih kod v direktnih produktih ciklov
Secondary abstract: Let ▫$G = \times_{i=1}^nC_{\ell_i}$▫ be a direct product of cycles. It is proved that for any ▫$r \ge 1$▫, and any ▫$n \ge 2$▫, each connected component of ▫$G$▫ contains an ▫$r$▫-perfect code provided that each ▫$\ell_i$▫ is a multiple of ▫$r^n + (r+1)^n▫$. On the other hand, if a code of ▫$G$▫ contains a given vertex and its canonical local vertices, then any ▫$\ell_i$▫ is a multiple of ▫$r^n + (r+1)^n$▫. It is also proved that an ▫$r$▫-perfect code ▫$(r \ge 2)$▫ of ▫$G$▫ is uniquely determined by ▫$n$▫ vertices, and it is conjectured that for ▫$r \ge 2$▫ no other codes in ▫$G$▫ exist other than the constructed ones.
Secondary keywords: matematika;teorija grafov;korekcijske kode;direktni produkt grafov;popolne kode;cikli;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 2-18
Volume: ǂVol. ǂ37
Issue: ǂiss. ǂ1
Chronology: 2006
ID: 1472803