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

B. A. Pogorelov ; M. A. Pudovkina

Diskretnaya Matematika, Tome 30 (2018) no. 4, pp. 66-87

Résumé

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.

Détail

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