Эта публикация цитируется в
8 статьях
Статьи
О совершенных $2$-раскрасках гиперкуба
К. В. Воробьёвa,
Д. Г. Фон-дер-Флаассb a Новосибирский государственный университет
b Институт математики им. С. Л. Соболева СО РАН
Аннотация:
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$.
Ключевые слова:
homogenization, nonlinear diffusion, compressible viscous fluid.
УДК:
517.95
MSC: 76S05 Поступила 22 декабря 2009 г., опубликована
10 марта 2010 г.