An almost complete description of perfect codes in direct products of cycles
type: Item
instance of: scholarly article
title: An almost complete description of perfect codes in direct products of cycles
zbMATH Open document ID: 1114.05073
author: Sandi Klavžar
author: Simon Špacapan
author: Janez Žerovnik
published in: Advances in Applied Mathematics
publication date: 2007-02-13T00:00:00Z
review text: The concept of perfect codes can be generalized to graphs in the obvious manner: an \(r\)-perfect code in a graph \(G\) is a set of vertices \(C \subseteq V(G)\) with the property that for any vertex \(v \in V(G)\), \(d(v,c) \leq r\) for exactly one vertex \(c \in C\). Two vertices \((v_1,v_2)\) and \((w_1,w_2)\) in the direct product of two graphs, \(G\) and \(H\), are adjacent whenever \(v_1w_1 \in E(G)\) and \(v_2w_2 \in E(H)\). The authors study perfect codes in the direct product of \(n \geq 2\) cycles, give a sufficient condition for the existence of such codes -- that the length of each cycle in the product is a multiple of \(r^n + (r+1)^n\) -- and finally conjecture that for \(r \geq 2\) the sufficient condition is also necessary (which is proved for \(n \leq 4\) and cycles of length at least \(2r+2\)).
reviewed by: Patric R. J. Östergård
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 94B60
zbMATH DE Number: 5125290
zbMATH Keywords: direct product of graphs
MaRDI profile type: Publication
full work available at URL: j.aam.2005.10.002
OpenAlex ID: W2056105229
cites work: Perfect codes in graphs
cites work: Error-correcting codes on the Towers of Hanoi graphs
cites work: Q4378631
cites work: Q4828516
cites work: Factoring cardinal product graphs in polynomial time
cites work: Q4523707
cites work: Characterizing \(r\)-perfect codes in direct products of two and three cycles
cites work: Perfect r-domination in the Kronecker product of three cycles
cites work: Perfect \(r\)-domination in the Kronecker product of two cycles, with an application to diagonal/toroidal mesh
cites work: Isomorphic components of Kronecker product of bipartite graphs
cites work: 1-perfect codes in Sierpiński graphs
cites work: Perfect codes over graphs
cites work: Q4892794
cites work: Regular codes in regular graphs are difficult
cites work: Q5284096
cites work: Perfect codes in direct products of cycles
cites work: Diagonal and toroidal mesh networks
cites work: The Kronecker Product of Graphs
DOI: 10.1016/J.AAM.2005.10.002
description: scientific article; zbMATH DE number 5125290