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 条
  • [1] Perfect 2-colorings of a hypercube
    D. G. Fon-Der-Flaass
    Siberian Mathematical Journal, 2007, 48 : 740 - 745
  • [2] ON PERFECT 2-COLORINGS OF THE HYPERCUBE
    Vorobev, K. V.
    Fon-Der-Flaass, D. G.
    SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2010, 7 : 65 - 75
  • [3] 2-COLORINGS THAT DECOMPOSE PERFECT GRAPHS
    CHVATAL, V
    LENHART, WJ
    SBIHI, N
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 49 (01) : 1 - 9
  • [4] Perfect 2-colorings of Hamming graphs
    Bespalov, Evgeny A.
    Krotov, Denis S.
    Matiushev, Aleksandr A.
    Taranenko, Anna A.
    Vorob'ev, Konstantin V.
    JOURNAL OF COMBINATORIAL DESIGNS, 2021, 29 (06) : 367 - 396
  • [5] Perfect 2-colorings of the generalized Petersen graph
    MEHDI ALAEIYAN
    HAMED KARAMI
    Proceedings - Mathematical Sciences, 2016, 126 : 289 - 294
  • [6] On the regularity of perfect 2-colorings of the Johnson graph
    I. Yu. Mogil’nykh
    Problems of Information Transmission, 2007, 43 : 303 - 309
  • [7] Perfect 2-colorings of the generalized Petersen graph
    Alaeiyan, Mehdi
    Karami, Hamed
    PROCEEDINGS OF THE INDIAN ACADEMY OF SCIENCES-MATHEMATICAL SCIENCES, 2016, 126 (03): : 289 - 294
  • [8] Perfect 2-colorings of transitive cubic graphs
    Avgustinovich S.V.
    Lisitsyna M.A.
    Journal of Applied and Industrial Mathematics, 2011, 5 (4) : 519 - 528
  • [9] Perfect 2-colorings of the Grassmann graph of planes
    De Winter, Stefaan
    Metsch, Klaus
    ELECTRONIC JOURNAL OF COMBINATORICS, 2020, 27 (01):
  • [10] On the ruegularity of perfect 2-colorings of the Johnson graph
    Mogil'nykh, I. Yu
    PROBLEMS OF INFORMATION TRANSMISSION, 2007, 43 (04) : 303 - 309
12345