On generalized truncations of complete graphs
Keywords:Truncation, vertex-transitive, Cayley graph, automorphism group
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 Kn 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 Kn 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.
Articles in this journal are published under Creative Commons Attribution 4.0 International License