RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2018 Volume 30, Issue 4, Pages 66–87 (Mi dm1487)

Classification of distance-transitive orbital graphs of overgroups of the Jevons group

B. A. Pogorelova, M. A. Pudovkinab

a Academy of Cryptography of Russian Federation
b Bauman Moscow State Technical University

Abstract: The Jevons group $A{\tilde S_n}$ is an isometry group of the Hamming metric on the $n$-dimensional vector space ${V_n}$ over $GF(2)$. It is generated by the group of all permutation $(n \times n)$-matrices over $GF(2)$ and the translation group on ${V_n}$. Earlier the authors of the present paper classified the submetrics of the Hamming metric on ${V_n}$ for $n \geqslant 4$, and all overgroups of $A{\tilde S_n}$ which are isometry groups of these overmetrics. In turn, each overgroup of $A{\tilde S_n}$ is known to define orbital graphs whose “natural” metrics are submetrics of the Hamming metric. The authors also described all distance-transitive orbital graphs of overgroups of the Jevons group $A{\tilde S_n}$. In the present paper we classify the distance-transitive orbital graphs of overgroups of the Jevons group. In particular, we show that some distance-transitive orbital graphs are isomorphic to the following classes: the complete graph ${K_{{2^n}}}$, the complete bipartite graph ${K_{{2^{n - 1}}{{,2}^{n - 1}}}}$, the halved $(n + 1)$-cube, the folded $(n + 1)$-cube, the graphs of alternating forms, the Taylor graph, the Hadamard graph, and incidence graphs of square designs.

Keywords: orbital graph, the Jevons group, distance-transitive graphs, Hamming graph, Taylor graph, Hadamard graph.

UDC: 519.172+512.542.7

Received: 28.11.2017

DOI: 10.4213/dm1487


 English version:
Discrete Mathematics and Applications, 2020, 30:1, 7–22

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025