On null completely regular codes in Manhattan metric

2025/05/15 by I. Yu. Mogilnykh, Mogilnykh, I. Yu., A. Yu. Vasil’eva +1
Computer Science · Engineering · Mathematics · #94B60 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #Information Theory (cs.IT) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2505.09893

openalex publication_date 2025/05/15 · openalex created_date 2025/10/15 · openalex updated_date 2026/07/28

Abstract

We investigate the class of completely regular codes in graphs with a distance partition C₀,..., C_ρ, where each set C_i, for 0<=i<=r-1, is an independent set. This work focuses on the existence problem for such codes in the n-dimensional infinite grid. We demonstrate that several parameter families of such codes necessarily arise from binary or ternary Hamming graphs or do not exist. Furthermore, employing binary linear programming techniques, we explore completely regular codes in infinite grids of dimensions 3 and 4 for the cases r=1 and r=2.

Citations

• Perfect colorings of Z²: Nine colors

Related

• Families of nested completely regular codes and distance-regular graphs
• On the existence of some completely regular codes in Hamming graphs
• Completely regular codes with different parameters and the same distance-regular coset graphs
• Completely regular codes in graphs covered by a Hamming graph
• Completely regular codes in Johnson and Grassmann graphs with small covering radii