Perfect 2-colorings of a hypercube

被引：42
|
作者：
Fon-Der-Flaass, D. G. [1 ]
机构：
[1] Sobolev Inst Math, Novosibirsk, Russia
来源：
SIBERIAN MATHEMATICAL JOURNAL | 2007年 / 48卷 / 04期
基金：
俄罗斯基础研究基金会;
关键词：
hypercube; coloring; perfect code;
D O I：
10.1007/s11202-007-0075-4
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A coloring of the vertices of a graph is called perfect if the multiset of colors of all neighbors of a vertex depends only on its own color. We study the possible parameters of perfect 2-colorings of the n-dimensional cube. Some necessary conditions are obtained for existence of such colorings. A new recursive construction of such colorings is found, which produces colorings for all known and infinitely many new parameter sets.
引用
收藏
页码：740 / 745
页数：6
相关论文
共 50 条
  • [31] Exponents of 2-colorings of loopless, symmetric digraphs
    Shao, Yanling
    Gao, Yubin
    LINEAR & MULTILINEAR ALGEBRA, 2009, 57 (01): : 65 - 74
  • [32] Monochromatic products and sums in 2-colorings of N
    Bowen, Matt
    ADVANCES IN MATHEMATICS, 2025, 462
  • [33] IRREGULARITIES OF 2-COLORINGS OF THE NXN SQUARE LATTICE
    BECK, J
    COMBINATORICA, 1982, 2 (02) : 111 - 123
  • [34] Combinatorial extremum problems for 2-colorings of hypergraphs
    A. P. Rozovskaya
    Mathematical Notes, 2011, 90
  • [35] Perfect 2-Colorings of Johnson Graphs J(6,3) and J(7,3)
    Avgustinovich, Sergey
    Mogilnykh, Ivan
    CODING THEORY AND APPLICATIONS, PROCEEDINGS, 2008, 5228 : 11 - +
  • [36] Monochrome symmetric subsets in 2-colorings of groups
    Gryshko, Y
    ELECTRONIC JOURNAL OF COMBINATORICS, 2003, 10 (01):
  • [37] BALANCED 2-COLORINGS OF FINITE SETS IN THE CUBE
    BECK, J
    DISCRETE MATHEMATICS, 1989, 73 (1-2) : 13 - 25
  • [38] Unavoidable patterns in 2-colorings of the complete bipartite graph
    Hansberg, Adriana
    Ventura, Denae
    XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, 2023, 224 : 166 - 174
  • [39] DISTANCES FORBIDDEN BY 2-COLORINGS OF Q3 AND AN
    CHOW, T
    DISCRETE MATHEMATICS, 1993, 115 (1-3) : 95 - 102
  • [40] 2-COLORINGS IN S(T, T + 1, V)
    GIONFRIDDO, M
    LO FARO, G
    DISCRETE MATHEMATICS, 1993, 111 (1-3) : 263 - 268
12345