Automorphisms and regular embeddings of merged Johnson graphs
type: Item
instance of: scholarly article
title: Automorphisms and regular embeddings of merged Johnson graphs
zbMATH Open document ID: 1063.05037
author: Gareth Jones
published in: European Journal of Combinatorics
publication date: 2005-03-08T00:00:00Z
review text: The vertices of the Johnson graph \(J(n,m)\) are the \(m\)-element subsets of an \(n\)-element set adjacent if their intersection has \(m-1\) elements. The distance \(i\) Johnson graph \(J(n,m)_i\) has the same set of vertices as \(J(n,m)\) with two vertices adjacent if they are of distance \(i\) in \(J(n,m)\). The merged Johnson graph \(J(n,m)_I\) is the edge-union of the graphs \(J(n,m)_i\), \( i \in I\), \( I \subseteq \{ 1,2, \dots, m \}\). The paper contains a full classification of the automorphism groups of generalized Johnson graphs. All of these graphs with the exception of \(J(12,4)\) with \(I= \{ 1,3 \}\) or \(I= \{ 2,4 \}\), \(J(n,(n-1)/2)\), and \(J(n,n/2)\), are shown to have their (full) automorphism group equal to \(S_n\) in its induced action on the \(m\)-element subsets of an \(n\)-element set. The proof is based on the classification of supergroups of \(S_n\) in its induced action completed by \textit{V. A. Ustimenko-Bakumovskij} [Sov. Math., Dokl. 18, 1433--1437 (1978; Zbl 0396.20002); translation from Dokl. Akad. Nauk SSSR 237, 276--279 (1977)]. Using this classification, the author succeeds at classifying all regular embeddings of merged Johnson graphs. Namely, it is shown that the only regular embeddings of merged Johnson graphs are the octahedral orientable embedding of \(J(4,2)_1\) and its non-orientable Petrie dual, two non-orientable embeddings of \(J(4,2)_{1,2} = K_6\), a Petrie dual pair of non-orientable embeddings of \(J(5,2)_1\), and a non-orientable embedding of Petersen \(J(5,2)_2\). It is also shown that none of the graphs \(J(n,m)_I\) where \( 5 \leq m < (n-1)/2 \) and \( \emptyset \subset I \subset \{ 1,2, \dots , m \} \) has a vertex-transitive embedding in an orientable or non-orientable surface.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 2142215
zbMATH Keywords: non-orientable embedding
reviewed by: Robert Jajcay
MaRDI profile type: Publication
full work available at URL: j.ejc.2004.01.012
OpenAlex ID: W1979668650
cites work: Q3840854
cites work: Automorphisms of imbedded graphs
cites work: Q3992965
cites work: Weak n-Homogeneity Implies Weak (n - 1)-Homogeneity
cites work: Q3684278
cites work: Q5672665
cites work: Q5650865
cites work: Q4882944
cites work: Symmetric Groups as Maximal Subgroups of Orthogonal and Symplectic Groups over the Field of Two Elements
cites work: Q4046238
cites work: On a Diophantine Equation
cites work: Q4284633
cites work: The double cosets of a finite group
cites work: Normalizers of p-subgroups in finite groups
cites work: Triply transitive groups in which only the identity fixes four letters
cites work: On certain maximal subgroups of symmetric or alternating groups
cites work: Q4284642
cites work: Q3325748
cites work: Regular orientable imbeddings of complete graphs
cites work: Q4325463
cites work: Operations on maps, and outer automorphisms
cites work: \(k\)-homogeneous groups
cites work: Transitivity of finite permutation groups on unordered sets
cites work: Regular embeddings of canonical double coverings of graphs
cites work: Graphs and finite permutation groups
cites work: On the maximality of \(S_ n\) in \(S_{\binom{n}{k}}\)
cites work: Q4179161
cites work: Kepler's small stellated dodecahedron as a Riemann surface
cites work: Q5512231
cites work: Operators over regular maps
cites work: Kennzeichnung endlicher linearer Gruppen als Permutationsgruppen
DOI: 10.1016/J.EJC.2004.01.012
description: scientific article; zbMATH DE number 2142215