On generalized truncations of complete graphs

Xue Wang, Fu-Gang Yin, Jin-Xin Zhou

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 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.


Keywords


Truncation, vertex-transitive, Cayley graph, automorphism group

Full Text:

PDF


DOI: https://doi.org/10.26493/1855-3974.2122.1e2

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications