On perfect colorings of the halved 24-cube

Abstract

A vertex 2-coloring of a graph is said to be perfect with parameters $(a_{ij}{)}_{i,j=1}^k$ if for every $i,j\in \{1,...,k\}$ every vertex of color $i$ is adjacent with exactly $a_{ij}$ vertices of color $j$. We consider the perfect 2-colorings of the distance-2 graph of the 24-cube $\{0,1{\}}^{24}$ with parameters $((20+c,256-c)(c,276-c))$ (i.e., with eigenvalue 20). We prove that such colorings exist for all $c$ from 1 to 128 except 1, 2, 4, 5, 7, 10, 13 and do not exist for $c=1,2,4,5,7$. Keywords: perfect coloring, equitable partition, hypercube, halved n-cube

Eng: 9p; Rus: 10p. V.2: case c=7 added; title changed; minor revision

Cited by in corpus (2)

• Equitable partitions of Latin-square graphs
• On completely regular codes of covering radius 1 in the halved hypercubes