Distance-2 MDS codes and latin colorings in the Doob graphs Научная публикация
| Журнал |
Graphs and Combinatorics
ISSN: 0911-0119 , E-ISSN: 1435-5914 |
||
|---|---|---|---|
| Вых. Данные | Год: 2018, Том: 34, Номер: 5, Страницы: 1001-1017 Страниц : 17 DOI: 10.1007/s00373-018-1926-4 | ||
| Ключевые слова | Doob graph, Maximum independent set, Maximum cut, MDS code, Latin hypercube, Equitable partition, Completely regular set | ||
| Авторы |
|
||
| Организации |
|
Реферат:
The maximum independent sets in the Doob graphs D(m, n) are analogs of the distance-2 MDS codes in Hamming graphs and of the latin hypercubes. We prove the characterization of these sets stating that every such set is semilinear or reducible. As related objects, we study vertex sets with maximum cut (edge boundary) in D(m, n) and prove some facts on their structure. We show that the considered two classes (the maximum independent sets and the maximum-cut sets) can be defined as classes of completely regular sets with specified 2-by-2 quotient matrices. It is notable that for a set from the considered classes, the eigenvalues of the quotient matrix are the maximum and the minimum eigenvalues of the graph. For D(m, 0), we show the existence of a third, intermediate, class of completely regular sets with the same property.
Библиографическая ссылка:
Krotov D.S.
, Bespalov E.A.
Distance-2 MDS codes and latin colorings in the Doob graphs
Graphs and Combinatorics. 2018. V.34. N5. P.1001-1017. DOI: 10.1007/s00373-018-1926-4 WOS Scopus РИНЦ OpenAlex
Distance-2 MDS codes and latin colorings in the Doob graphs
Graphs and Combinatorics. 2018. V.34. N5. P.1001-1017. DOI: 10.1007/s00373-018-1926-4 WOS Scopus РИНЦ OpenAlex
Даты:
| Поступила в редакцию: | 15 нояб. 2016 г. |
| Опубликована online: | 17 июл. 2018 г. |
Идентификаторы БД:
| Web of science: | WOS:000442695700010 |
| Scopus: | 2-s2.0-85049966141 |
| РИНЦ: | 35752825 |
| OpenAlex: | W2269337634 |