On the classification of distance-transitive orbital graphs of overgroups of the jevons group.pdf Группа экспоненцирования S2 t Sn, называемая также группой Джевонса, совпадает с группой ASn, порождённой группой сдвигов на n-мерном векторном пространстве Vn над полем GF(2) и группой подстановочных (пх п)-матриц Sn над полем GF(2). Группа Джевонса встречается в теории кодирования, теории графов, теории булевых функций, алгебраической комбинаторике и криптографии; в частности, она - является группой изометрий метрики Хемминга на Vn; - описывает множество преобразований, не распространяющих искажения; - является группой инерции множества всех бент-функций. Для группы подстановок G ^ S2 t Sn рассматривается также её естественное действие на упорядоченных парах векторов из пространства Vn. Орбиты при таком действии называются орбиталами. Каждому орбиталу Г ставится в соответствие граф Г = (Vn, Г) с множеством вершин Vn и множеством рёбер Г, называемый графом орбитала. В алгебраической комбинаторике группа Джевонса связана со схемой отношений Хемминга [1] на пространстве Vn, которая может задаваться алгеброй матриц смежности графов орбиталов группы ASn. При этом орбиталы пронумерованы таким образом, что орбита стабилизатора нулевого вектора группы ASn совпадает с множеством A(n) С Vn всех векторов веса Хемминга i, а i-й орбитал есть Г(п) = |(в, в') G V2 : в Ф в' G A(n) j для всех i G {0,... , n}, где ф - бинарная операция покоординатного сложения векторов из V„. В [2, 3] проведена классификация всех надгрупп G группы ASn, ASn ^ G ^ S(Vn), для n ^ 4. Она позволила в [4, 5] описать графы орбиталов всех надгрупп группы Джевонса и их группы автоморфизмов. В [5] среди графов орбиталов надгрупп группы Джевонса описаны графы, принадлежащие к таким известным классам, как дистанционно-транзитивные, антиподальные и двудольные. Заметим, что классификации дистанционно-транзитивных графов уделяется повышенное внимание более 40 лет (см. [1, 6-10] и др.). Это зачастую вызвано тем, что не только некоторые известные графы дистанционно-транзитивны, но также некоторые интересные группы являются группами автоморфизмов дистанционно-транзитивных графов. Так, дистанционно-транзитивными являются графы Хемминга, Джонсона, Гроссманна, полный двудольный и т. д. Описаны (см., например, [6]) все дистанционно-транзитивные графы, степени вершин которых не превосходят 13. Заметим, что из полной классификации групп ранга 3 [11] следует описание групп автоморфизмов дистанционно-транзитивных графов диаметра 2, называемых сильно регулярными. В данной работе проводится классификация дистанционно-транзитивных графов орбиталов надгрупп группы Джевонса. Показано, что среди дистанционно-транзитивных графов орбиталов надгрупп группы Джевонса имеются графы, изоморфные следующим графам: 1) полному графу K2n; 2) полному двудольному графу K2n-i,2n-i; 3) половинному (n + 1)-кубу; 4) сложенному (n + 1)-кубу; 5) сложенному половинному (n + 2)-кубу; 6) графам знакопеременных форм; 7) графу Тейлора (для графов диаметра 3); 8) дополнению 2 х 2"-1-решётки (для графов диаметра 3); 9) дополнению графа 2n-1K2, состоящего из 2n-1 двухвершинных компонент связности; 10) графу Адамара (для графов диаметра 4); 11) графам инцидентности 2-(2n-1, u(n), 2u(n-2)) блок-схем (для графов диаметра 3 при нечётном n ^ 5), i G {1, 3}, где j = S (4k + J, j = 12 3 При этом графы диаметра 2 изоморфны одному из следующих классов графов: 1) графу K2n-i,2n-i; 2) дополнению графа 2n-1K2; 3) графам знакопеременных форм, группы автоморфизмов которых изоморфны ортогональным группам AOn1), AOn2) при чётном n.

Скачать электронную версию публикации