On completely regular codes with minimum eigenvalue in geometric graphs

DOI10.1016/J.DISC.2023.113357zbMATH Open1518.05050arXiv2210.11184MaRDI QIDQ6041848FDOQ6041848

Authors: Ivan Yu. Mogilnykh, Konstantin Vorob'ev 

Publication date: 15 May 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We prove that any completely regular code with minimum eigenvalue in any geometric graph G corresponds to a completely regular code in the clique graph of G. Studying the interrelation of these codes, a complete characterization of the completely regular codes in the Johnson graphs J(n,w) with covering radius w-1 and strength 1 is obtained. In particular this result finishes a characterization of the completely regular codes in the Johnson graphs J(n,3). We also classify the completely regular codes of strength 1 in the Johnson graphs J(n,4) with only one case for the eigenvalues left open.

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

Recommendations

• Completely regular codes in Johnson and Grassmann graphs with small covering radii
• An algebraic characterization of completely regular codes in distance-regular graphs
• Arithmetic completely regular codes
• Completely regular codes
• New families of completely regular codes and their corresponding distance regular coset graphs

zbMATH Keywords

completely regular codereconstruction\(t\)-designgeometric graphJohnson graphDelsarte clique

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Other designs, configurations (05B30) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62) Linear codes (general theory) (94B05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Completely regular clique graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Perfect 2-Colorings of Johnson Graphs J(6,3) and J(7,3)
• On perfect 2-colorings of Johnson graphs \(J(v, 3)\)
• On the existence of 2-designs Slambda(2,3,v) without repeated blocks
• Completely regular designs
• To the theory of \(q\)-ary Steiner and other-type trades
• Cycle-balance conditions for distance-regular graphs
• Completely regular designs of strength one
• Induced perfect colorings
• Boolean degree 1 functions on some classical association schemes
• On completely regular codes
• Completely regular codes in Johnson and Grassmann graphs with small covering radii
• Equitable 2-partitions of the Hamming graphs with the second eigenvalue

Cited In (8)

• A new infinite series of regular uniformly geodetic code graphs
• \(L_{\infty}\) norm minimization for nowhere-zero integer eigenvectors of the block graphs of Steiner triple systems and Johnson graphs
• On a conjecture of Martin on the parameters of completely regular codes and the classification of the completely regular codes in the biggs-smith graph
• An algebraic characterization of completely regular codes in distance-regular graphs
• Completely regular codes in Johnson and Grassmann graphs with small covering radii
• Arithmetic completely regular codes
• Completely regular codes with covering radius 1 and the second eigenvalue in 3-dimensional Hamming graphs
• On the number of minimal codewords in codes generated by the adjacency matrix of a graph

This page was built for publication: On completely regular codes with minimum eigenvalue in geometric graphs

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