Distance-2 MDS codes and Latin colorings in the Doob graphs

DOI10.1007/S00373-018-1926-4MaRDI QIDQ1756044zbMATH OpenOpenAlexWikidataFDO

Authors Denis S. Krotov, Evgeniĭ Andreevich Bespalov

Publication date 11 January 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.01429

zbMATH Keywords

completely regular setDoob graphequitable partitionLatin hypercubemaximum cutmaximum independent setMDS code

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial codes (94B25)

Abstract: The maximum independent sets in the Doob graphs D(m,n) are analogs of the distance-2 MDS codes in Hamming graphs and of the latin hypercubes. We prove the characterization of these sets stating that every such set is semilinear or reducible. As related objects, we study vertex sets with maximum cut (edge boundary) in D(m,n) and prove some facts on their structure. We show that the considered two classes (the maximum independent sets and the maximum-cut sets) can be defined as classes of completely regular sets with specified 2-by-2 quotient matrices. It is notable that for a set from the considered classes, the eigenvalues of the quotient matrix are the maximum and the minimum eigenvalues of the graph. For D(m,0), we show the existence of a third, intermediate, class of completely regular sets with the same property.

Recommendations

• MDS codes in Doob graphs
• Tight 2-designs and perfect 1-codes in Doob graphs
• Distance-regular graphs, MH-colourings and MLD-colourings
• The 2-distance coloring of the Cartesian product of cycles using optimal Lee codes
• The Existence of Perfect Codes in Doob Graphs
• Low-density MDS codes and factors of complete graphs
• On paving matroids and a generalization of MDS codes
• scientific article; zbMATH DE number 1803166
• 2-distance colorings of integer distance graphs

Cites work

• n-ary quasigroups of order 4.
• A bound on correlation immunity
• Arithmetic completely regular codes
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 5379405 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 5228046 (Why is no real title available?)
• MDS codes in Doob graphs
• On \(r\)-partition designs in Hamming spaces
• On decomposability of 4-ary distance 2 MDS codes, double-codes, and \(n\)-quasigroups of order 4
• On extensions of partial \(n\)-quasigroups of order 4.
• On reducibility of n-ary quasigroups
• On the number of maximum independent sets in Doob graphs
• Perfect colorings of the 12-cube that attain the bound on correlation immunity

Cited in

(4)

• Tight 2-designs and perfect 1-codes in Doob graphs
• Additive perfect codes in Doob graphs
• MDS codes in Doob graphs
• On the number of maximum independent sets in Doob graphs

This page was built for publication: Distance-2 MDS codes and Latin colorings in the Doob graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756044)