On generalized truncations of complete graphs

Abstract

For a k-regular graph Γ and a graph Υ of order k, a generalized truncation of Γ by Υ is constructed by replacing each vertex of Γ with a copy of Υ. E. Eiben, R. Jajcay and P. Šparl introduced a method for constructing vertex-transitive generalized truncations. For convenience, we call a graph obtained by using Eiben et al.’s method a special generalized truncation. In their paper, Eiben et al. proposed a problem to classify special generalized truncations of a complete graph K_n by a cycle of length n − 1. In this paper, we completely solve this problem by demonstrating that with the exception of n = 6, every special generalized truncation of a complete graph K_n by a cycle of length n − 1 is a Cayley graph of AGL(1, n) where n is a prime power. Moreover, the full automorphism groups of all these graphs and the isomorphisms among them are determined.