A Construction for Vertex-Transitive Graphs

Abstract

A useful general strategy for the construction of interesting families of vertex-transitive graphs is to begin with some family of transitive permutation groups and to construct for each group Γ in the family all graphs G whose vertex–set is the orbit V of Γ and for which Γ ≦ Aut ( G ), where Aut ( G ) denotes the automorphism group of G . For example, if we consider the family of cyclic groups 〈(0 1 … n – 1)〉 generated by cycles (0, 1 … n – 1) of length n , then the corresponding graphs are the n -vertex circulant graphs. In this paper we consider transitive permutation groups of degree mn generated by a “rotation” ρ which is a product of m disjoint cycles of length n and by a “twisted translation” t ; such that τρτ –l = ρ α for some α.