Equitable 2-partitions of the Hamming graphs with the second eigenvalue

DOI10.1016/J.DISC.2020.112039MaRDI QIDQ2198380zbMATH OpenOpenAlexFDO

Authors Alexandr Valyuzhenich, Ivan Yu. Mogilnykh

Publication date 10 September 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

completely regular codeeigenvalue techniqueequitable partitionHamming graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The eigenvalues of the Hamming graph $H(n,q)$ are known to be $lambd{a}_i(n,q)=(q-1)n-qi$, $0leqileqn$. The characterization of equitable 2-partitions of the Hamming graphs $H(n,q)$ with eigenvalue $lambd{a}_1(n,q)$ was obtained by Meyerowitz in [15]. We study the equitable 2-partitions of $H(n,q)$ with eigenvalue $lambd{a}_2(n,q)$. We show that these partitions are reduced to equitable 2-partitions of $H(3,q)$ with eigenvalue $lambd{a}_2(3,q)$ with exception of two constructions.

Recommendations

• On 2-equitable graphs
• Local duality for equitable partitions of a Hamming space
• scientific article; zbMATH DE number 524126
• Characterizing imprimitive partition designs of binary Hamming graphs
• Partition designs with two subsets of the Hamming space

Cites work

• A bound on correlation immunity
• Arithmetic completely regular codes
• Completely regular designs of strength one
• Cycle-balance conditions for distance-regular graphs
• Existence of q-analogs of Steiner systems
• scientific article; zbMATH DE number 5379405 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 26596 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• Minimum supports of eigenfunctions of Hamming graphs
• Minimum supports of functions on the Hamming graphs with spectral constraints
• On \(q\)-ary linear completely regular codes with \(\rho=2\) and antipodal dual
• On completely regular codes
• On nonsystematic perfect binary codes.
• On perfect colorings of Boolean \(n\)-cube and correlation immune functions with small density
• On unbalanced Boolean functions with best correlation immunity
• Perfect colorings of the 12-cube that attain the bound on correlation immunity
• Tactical decompositions and orbits of projective groups

Cited in

(19)

• Characterizing imprimitive partition designs of binary Hamming graphs
• Equitable factorizations of Hamming shells
• Completely regular codes in Johnson and Grassmann graphs with small covering radii
• Subgroup regular sets in Cayley graphs
• scientific article; zbMATH DE number 524126 (Why is no real title available?)
• scientific article; zbMATH DE number 1373450 (Why is no real title available?)
• On 2-equitable graphs
• A Bound on Equitable Partitions of the Hamming Space
• Minimum supports of eigenfunctions of graphs: a survey
• On completely regular codes with minimum eigenvalue in geometric graphs
• Perfect 2‐colorings of Hamming graphs
• Local duality for equitable partitions of a Hamming space
• On degree-3 and (n - 4)-correlation-immune perfect colorings of n-cubes
• On reduction for eigenfunctions of graphs
• Completely regular codes with covering radius 1 and the second eigenvalue in 3-dimensional Hamming graphs
• Regular sets in Cayley sum graphs
• An upper bound on the number of relevant variables for Boolean functions on the Hamming graph
• On the subgroup regular sets in Cayley graphs
• Equitable 2-partitions of the Johnson graphs J(n,3)

This page was built for publication: Equitable 2-partitions of the Hamming graphs with the second eigenvalue

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