2019/12/19 by I. Yu. Mogilnykh, Mogilnykh, I. Yu., F. I. Solov’eva +2
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #cs.IT #graph theory and CDMA systems #math.CO #math.IT
paper · pdf · doi:10.48550/arxiv.1912.09089
arxiv created 2019/12/19 · openalex publication_date 2019/12/19 · arxiv updated 2019/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A pair (T0,T1) of disjoint sets of vertices of a graph G is called a perfect bitrade in G if any ball of radius 1 in G contains exactly one vertex in T0 and T1 or none simultaneously. The volume of a perfect bitrade (T0,T1) is the size of T0. In particular, if C0 and C1 are distinct perfect codes with minimum distance 3 in G then (C0∖ C1,C1∖ C0) is a perfect bitrade. For any q≥ 3, r≥ 1 we construct perfect bitrades in the Hamming graph H(qr+1,q) of volume (q!)r and show that for r=1 their volume is minimum.