Perfect 2-colorings of Hamming graphs

Evgeny A. Bespalov, Denis S. Krotov, Aleksandr A. Matiushev, Anna A. Taranenko, Konstantin V. Vorob'ev

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

We consider the problem of existence of perfect 2-colorings (equitable 2-partitions) of Hamming graphs with given parameters. We start with conditions on parameters of graphs and colorings that are necessary for their existence. Next we observe known constructions of perfect colorings and propose some new ones giving new parameters. At last, we deduce which parameters of colorings are covered by these constructions and give tables of admissible parameters of 2-colorings in Hamming graphs (Formula presented.) for small (Formula presented.) and (Formula presented.). Using the connection with perfect colorings, we construct an orthogonal array OA(2048, 7, 4, 5).

Original languageEnglish
Pages (from-to)367-396
Number of pages30
JournalJournal of Combinatorial Designs
Volume29
Issue number6
DOIs
Publication statusPublished - Jun 2021
Externally publishedYes

Keywords

  • equitable partition
  • graph covering
  • Hamming graph
  • perfect code
  • perfect coloring

OECD FOS+WOS

  • 1.01 MATHEMATICS

Fingerprint

Dive into the research topics of 'Perfect 2-colorings of Hamming graphs'. Together they form a unique fingerprint.

Cite this