Characterizing r-perfect codes in direct products of two and three cycles |
| |
Authors: | Janja Jerebic Sandi Klav?ar Simon Špacapan |
| |
Affiliation: | a Department of Mathematics and Computer Science, PEF, University of Maribor, Koroška cesta 160, 2000 Maribor, Slovenia b University of Maribor, FME, Smetanova 17, 2000 Maribor, Slovenia |
| |
Abstract: | An r-perfect code of a graph G=(V,E) is a set C⊆V such that the r-balls centered at vertices of C form a partition of V. It is proved that the direct product of Cm and Cn (r?1, m,n?2r+1) contains an r-perfect code if and only if m and n are each a multiple of 2(r+1)+r2 and that the direct product of Cm, Cn, and C? (r?1, m,n,??2r+1) contains an r-perfect code if and only if m, n, and ? are each a multiple of r3+3(r+1). The corresponding r-codes are essentially unique. Also, r-perfect codes in C2r×Cn (r?2, n?2r) are characterized. |
| |
Keywords: | Combinatorial problems Perfect r-domination Error-correcting codes Direct products of graphs |
本文献已被 ScienceDirect 等数据库收录! |
|