Perfect 2-colorings of Hamming graphs

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

doi:10.1002/jcd.21771

Perfect 2-colorings of Hamming graphs

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

Результат исследования: Научные публикации в периодических изданиях › статья › рецензирование

Аннотация

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).

Язык оригинала	английский
Журнал	Journal of Combinatorial Designs
DOI	https://doi.org/10.1002/jcd.21771
Состояние	Принято в печать - 2021
Опубликовано для внешнего пользования	Да

Предметные области OECD FOS+WOS

1.01 МАТЕМАТИКА

Доступ к документу

10.1002/jcd.21771

Ссылка на публикацию в Scopus

Fingerprint Подробные сведения о темах исследования «Perfect 2-colorings of Hamming graphs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

@article{3d7324728bd942d898172d7a704eaa76,

title = "Perfect 2-colorings of Hamming graphs",

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).",

keywords = "equitable partition, graph covering, Hamming graph, perfect code, perfect coloring",

author = "Bespalov, {Evgeny A.} and Krotov, {Denis S.} and Matiushev, {Aleksandr A.} and Taranenko, {Anna A.} and Vorob'ev, {Konstantin V.}",

note = "Funding Information: This study was funded by the Russian Science Foundation under grant 18‐11‐00136 (Sections 1–A.2, except Theorems 4.13 and 4.14 (1), whose early versions occurred as a part of the graduate thesis of Aleksandr Matiushev in the Novosibirsk State University); the work of Anna Taranenko was supported in part (Section A.3) by an award of the contest “Young Russian Mathematics.” Publisher Copyright: {\textcopyright} 2021 Wiley Periodicals LLC Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",

year = "2021",

doi = "10.1002/jcd.21771",

language = "English",

journal = "Journal of Combinatorial Designs",

issn = "1063-8539",

publisher = "Wiley-Blackwell",

}

TY - JOUR

T1 - Perfect 2-colorings of Hamming graphs

AU - Bespalov, Evgeny A.

AU - Krotov, Denis S.

AU - Matiushev, Aleksandr A.

AU - Taranenko, Anna A.

AU - Vorob'ev, Konstantin V.

N1 - Funding Information: This study was funded by the Russian Science Foundation under grant 18‐11‐00136 (Sections 1–A.2, except Theorems 4.13 and 4.14 (1), whose early versions occurred as a part of the graduate thesis of Aleksandr Matiushev in the Novosibirsk State University); the work of Anna Taranenko was supported in part (Section A.3) by an award of the contest “Young Russian Mathematics.” Publisher Copyright: © 2021 Wiley Periodicals LLC Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021

Y1 - 2021

N2 - 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).

AB - 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).

KW - equitable partition

KW - graph covering

KW - Hamming graph

KW - perfect code

KW - perfect coloring

UR - http://www.scopus.com/inward/record.url?scp=85102249444&partnerID=8YFLogxK

U2 - 10.1002/jcd.21771

DO - 10.1002/jcd.21771

M3 - Article

AN - SCOPUS:85102249444

JO - Journal of Combinatorial Designs

JF - Journal of Combinatorial Designs

SN - 1063-8539

ER -