|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2010, Volume 7, Pages 65–75
(Mi semr228)
|
|
|
|
This article is cited in 8 scientific papers (total in 8 papers)
Research papers
On perfect $2$-colorings of the hypercube
K. V. Vorobeva, D. G. Fon-Der-Flaassb a Novosibirsk State University
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Abstract:
A vertex coloring of a graph is called perfect if the multiset of colors appearing on the neighbours
of any vertex depends only on the color of the vertex. The parameters of a perfect coloring are thus given by a $n\times n$ matrix, where $n$ is the number of colors.
We give a recursive construction which can produce many different perfect colorings of the hypercube $H_n $ with $2$ colors and the parameters
$\left({ \begin{array}{ll}
a & b\\c & d
\end{array} }\right)$ satisfying the conditions $({b,c})=1,b+c=2^m$, $c>1$. In particular, this construction allows one to find many non-isomorphic perfect colorings with the parameters
$\left(
{ \begin{array}{ll}
k\cdot a & k\cdot b \\ k\cdot c & k\cdot d
\end{array} }\right)$.
For the parameters $\left({ \begin{array}{ll}
a & b\\c & d
\end{array} }\right)$ satisfying the extra condition $a\ge c-({b,c})$, we find a lower bound on the number of
produced colorings which is hyperexponential in $n$.
Keywords:
Hypercube, perfect coloring, perfect code.
Received December 22, 2009, published March 10, 2010
Citation:
K. V. Vorobev, D. G. Fon-Der-Flaass, “On perfect $2$-colorings of the hypercube”, Sib. Èlektron. Mat. Izv., 7 (2010), 65–75
Linking options:
https://www.mathnet.ru/eng/semr228 https://www.mathnet.ru/eng/semr/v7/p65
|
Statistics & downloads: |
Abstract page: | 533 | Full-text PDF : | 138 | References: | 57 |
|