Vertex transitive graphs from injective linear mappings

Mačaj, Martin

Journal of Algebraic Combinatorics, Tome 40 (2014) no. 4, pp. 983-999.

Résumé

Based on a motivation coming from the study of the metric structure of the category of finite dimensional vector spaces over a finite field $\mathbb F$, we examine a family of graphs, defined for each pair of integers $1\leq k\leq n$, with vertex set formed by all injective linear transformations $\mathbb F^k\to\mathbb F^n$ and edges corresponding to pairs of mappings, $f$ and $g$, with $\lambda(f,g)=\dim\mathrm{Im}(f-g)=1$. For $\mathbb F\cong\mathrm{GF}(q)$, this graph will be denoted by $\mathrm{INJ}_q(k,n)$. We show that all such graphs are vertex transitive and Hamiltonian and describe the full automorphism group of each $\mathrm{INJ}_q(k,n)$ for $k$. Using the properties of line-transitive groups, we completely determine which of the graphs $\mathrm{INJ }_q(k,n)$ are Cayley and which are not. The Cayley ones consist of three infinite families, corresponding to pairs $(1,n)$, $(n-1,n)$, and $(n,n)$, with $n$ and $q$ arbitrary, and of two sporadic examples $\mathrm{INJ}_2(2,5)$ and $\mathrm{INJ}_2(3,5)$. Hence, the overwhelming majority of our graphs is not Cayley.

Détail

Classification : 05C25, 05C60
Keywords: vertex transitive graphs, Cayley graphs, linear mappings