|
Классификация дистанционно транзитивных графов орбиталов надгрупп группы Джевонса
Б. А. Погореловa, М. А. Пудовкинаb a Академия криптографии Российской Федерации
b МГТУ имени Н. Э. Баумана (Национальный исследовательский университет)
Аннотация:
Группа Джевонса является группой изометрий метрики Хемминга на $n$-мерном векторном пространстве $V_{n}$ над полем $GF(2)$. Она порождена группой сдвигов пространства $V_{n}$ и группой подстановочных $(n \times n)$-матриц над полем $GF(2)$. Ранее авторы провели классификацию подметрик метрики Хемминга на ${V_n}$ для $n \geqslant 4$, а также всех надгрупп $G$ группы Джевонса, являющихся группами изометрий данных надметрик. В свою очередь, каждая надгруппа $G$ задаёт графы орбиталов, «естественными» метриками которых являются подметрики метрики Хемминга. Среди графов орбиталов надгрупп группы Джевонса авторами были выявлены все дистанционно транзитивные графы. В данной работе проводится классификация дистанционно транзитивных графов орбиталов надгрупп группы Джевонса. В том числе показано, что некоторые графы изоморфны следующим графам: полному графу ${K_{{2^n}}}$, полному двудольному графу ${K_{{2^{n - 1}}{{,2}^{n - 1}}}}$, половинному $(n + 1)$-кубу, сложенному $(n + 1)$-кубу, графам знакопеременных форм, графу Тейлора, графу Адамара, графам инцидентности блок-схем.
Ключевые слова:
граф орбитала, группа Джевонса, дистанционно транзитивные графы, граф Хемминга, граф Тейлора, граф Адамара.
Статья поступила: 28.11.2017
Образец цитирования:
Б. А. Погорелов, М. А. Пудовкина, “Классификация дистанционно транзитивных графов орбиталов надгрупп группы Джевонса”, Дискрет. матем., 30:4 (2018), 66–87; Discrete Math. Appl., 30:1 (2020), 7–22
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1487https://doi.org/10.4213/dm1487 https://www.mathnet.ru/rus/dm/v30/i4/p66
|
Статистика просмотров: |
Страница аннотации: | 387 | PDF полного текста: | 73 | Список литературы: | 49 | Первая страница: | 28 |
|