Quasi Perfect Codes in the Cartesian Product of Some Graphs

Basic Information

• Paper ID: 2510.13613
• Title: Quasi Perfect Codes in the Cartesian Product of Some Graphs
• Authors: S. A. Mane, N. V. Shinde
• Classification: math.CO (Combinatorics)
• Publication Date: October 15, 2025
• Paper Link: https://arxiv.org/abs/2510.13613

Abstract

An important problem in quasi-perfect code research is whether such codes can be constructed for all possible lengths n. This paper addresses this question for specific values of n. First, given that graph G admits a perfect code, the paper investigates the existence of quasi-perfect codes in the Cartesian product of G with paths (or cycles). Second, it explores quasi-perfect codes in the Cartesian products of two or three cycles $C_m\square C_n$ and $C_m\square C_n\square C_l$, as well as quasi-perfect codes in the Cartesian products of two or three paths $P_m\square P_n$ and $P_m\square P_n\square P_l$.

Research Background and Motivation

1. Problem to be Solved: This research aims to address the existence problem of quasi-perfect code construction, particularly systematic methods for constructing quasi-perfect codes in Cartesian products of graphs.
2. Problem Significance:
   • Perfect codes play a central role in error-correcting code theory but are relatively rare
   • The Golomb-Welch conjecture asserts that no perfect Lee e-error-correcting codes exist for length n≥3 and e>1
   • Quasi-perfect codes serve as important theoretical and practical approximations to perfect codes
3. Limitations of Existing Methods:
   • Existence conditions for quasi-perfect codes remain quite restrictive
   • Few quasi-perfect codes with covering radius greater than 3 are known
   • Lack of systematic construction methods
4. Research Motivation: Develop techniques for constructing quasi-perfect codes in G□H based on perfect codes in graph G, where H is a specific graph.

Core Contributions

1. Proposed a systematic method for constructing quasi-perfect codes from perfect codes: If graph G admits a perfect e-error-correcting code, then quasi-perfect e-error-correcting codes can be constructed in G□Pn or G□Cn
2. Constructed various concrete quasi-perfect codes:
   • Quasi-perfect 2-error-correcting codes in Pm□Pn□P6k-2 and Cm□Cn□C6k
   • Quasi-perfect codes in P4□P4□P4 based on perfect codes in P2□P2□P2
3. Extended known results: Constructed quasi-perfect codes in Cn□Cn□Cl (3≤n≤19) utilizing known quasi-perfect codes in Cn□Cn
4. Provided a complete theoretical framework: Systematically analyzed construction methods for quasi-perfect codes in Cartesian products of paths and cycles

Methodology Details

Task Definition

Given a graph G, construct quasi-perfect codes in its Cartesian products with paths Pn or cycles Cn, i.e., G□Pn and G□Cn. A code D is t-quasi-perfect if and only if it is t-error-correcting and has covering radius t+1.

Core Construction Methods

1. Basic Construction Theorem (Theorem 3.1)

For a perfect e-error-correcting code D in graph G:

• When e=1: Quasi-perfect 1-error-correcting codes can be constructed in G□P3k and G□C3k
• When e≥2: Quasi-perfect e-error-correcting codes can be constructed in G□P3 and G□C3

Construction Method:

D' = D ⊕ {1}

where ⊕ denotes the Cartesian product of sets.

2. Three-Dimensional Extension Construction (Theorem 3.2)

For a perfect 2-error-correcting code D1 in Pm□Pn, construct a quasi-perfect 2-error-correcting code in Pm□Pn□P6k-2:

Steps:

1. Define D2 = (0,3) + D1 (shifted code)
2. Construct D = (D1⊕{0}) ∪ (D2⊕{3})
3. Extend to larger dimensions: C = ⋃(i=0 to k-1)(D1⊕{6i} ∪ D2⊕{6i+3})

3. Cycle Product Construction

Theorem 3.6: Construct quasi-perfect 1-error-correcting codes in C3□C6□C4k

D0 = {(0,0), (1,2), (2,4)}
D1 = {(2,1), (0,3), (1,5)}
C = ⋃(i=0 to k-1)(D0⊕{4i} ∪ D1⊕{4i+2})

Technical Innovations

1. Hierarchical Construction Strategy: Decompose high-dimensional graphs into low-dimensional layers and apply known perfect codes within each layer
2. Shifting Technique: Ensure minimum distance is maintained between codewords in different layers through appropriate shift operations
3. Periodic Extension: Achieve constructions of arbitrary size through periodic repetition of basic construction blocks

Experimental Setup

Verification Methods

The paper primarily verifies construction correctness through theoretical proofs, supplemented by computer search for specific cases:

1. Theoretical Verification: Prove the minimum distance and covering radius of constructed codes
2. Computer Verification: For complex cases (e.g., certain parameters in Theorem 4.4), use computer search to verify

Evaluation Metrics

• Minimum Distance: The minimum distance between any two codewords
• Covering Radius: The maximum distance from any vertex to the nearest codeword
• Quasi-Perfection: Verify that covering radius = error-correcting capability + 1

Experimental Results

Main Results

1. Results from Theorem 3.1:
   • For e=1, successfully constructed quasi-perfect 1-error-correcting codes in G□P3k and G□C3k
   • For e≥2, successfully constructed quasi-perfect e-error-correcting codes in G□P3 and G□C3
2. Three-Dimensional Construction Results:
   • Constructed quasi-perfect 2-error-correcting codes in Pm□Pn□P6k-2 (Theorem 3.2)
   • Constructed quasi-perfect 2-error-correcting codes in Cm□Cn□C6k (Corollary 3.3)
3. Concrete Examples:
   • Perfect 1-error-correcting codes in C6□C6□C2 (Theorem 4.2)
   • Quasi-perfect 1-error-correcting codes in C3□C6□C4k (Theorem 3.6)

Construction Summary Table

Case Analysis

The paper provides multiple concrete construction examples, such as:

• Figure 1 illustrates quasi-perfect 1-error-correcting codes in P4□P4□P4
• Figures 2-6 illustrate quasi-perfect code constructions in various cycle products

Related Work

1. Perfect Code Theory: Based on Livingston and Stout's perfect dominating set theory
2. Codes in Lee Metric: Research direction driven by the Golomb-Welch conjecture
3. Quasi-Perfect Code Construction: Construction work by AlBdaiwi et al. in Lee metric
4. Codes in Graph Theory: Error-correcting code theory based on graph distance

Conclusions and Discussion

Main Conclusions

1. Successfully established a systematic method for constructing quasi-perfect codes from perfect codes
2. Provided explicit constructions of quasi-perfect codes for various Cartesian products of graphs
3. Extended known results on the existence of quasi-perfect codes

Limitations

1. Construction methods depend on the existence of perfect codes in base graphs
2. Constructions for certain parameter ranges still require computer verification
3. Applicability of construction methods to general graph Cartesian products is limited

Future Directions

1. Determine for which integers n and graphs G2, quasi-perfect codes can be constructed in Cartesian products of G1 with n copies of G2
2. Identify all parameter values (m,n,l) such that Cm□Cn□Cl admits quasi-perfect codes
3. Generalize to more general graph classes and metric spaces

In-Depth Evaluation

Strengths

1. Theoretical Rigor: All constructions have complete mathematical proofs
2. Systematic Approach: Provides a unified construction framework
3. Practical Value: Construction methods are applicable to multiple concrete cases
4. Visual Aids: Rich illustrations help understand the construction process

Weaknesses

1. Limited Scope: Methods primarily apply to Cartesian products of paths and cycles
2. Computational Complexity: Verification of certain constructions requires substantial computation
3. Optimality: Does not discuss optimality of constructed codes

Impact

1. Theoretical Contribution: Provides new construction techniques for quasi-perfect code theory
2. Application Prospects: Potential applications in network coding and distributed storage
3. Extensibility: Construction methods provide foundation for further research

Applicable Scenarios

1. Scenarios requiring deployment of error-correcting codes in regular network topologies
2. Error control in multi-dimensional grids and toroidal networks
3. Fault-tolerant resource placement in distributed systems

References

The paper cites 33 related references, primarily including:

• Golomb & Welch (1970): Pioneering work on perfect codes in Lee metric
• AlBdaiwi & Bose (2003): Quasi-perfect Lee distance codes
• Livingston & Stout (1990): Perfect dominating set theory
• Multiple recent studies on quasi-perfect code construction

Overall Assessment: This is a high-quality paper at the intersection of combinatorics and coding theory, providing systematic quasi-perfect code construction methods with rigorous theory and considerable practical value, establishing a solid foundation for further development in this field.