On automorphism groups of graph truncations

Brian Alspach, Edward Dobson


It is well known that the Petersen graph, the Coxeter graph, as well as the graphs obtained from these two graphs by replacing each vertex with a triangle, are trivalent vertex-transitive graphs without Hamilton cycles, and are indeed the only known connected vertex-transitive graphs of valency at least two without Hamilton cycles. It is known by many that the replacement of a vertex with a triangle in a trivalent vertex-transitive graph results in a vertex-transitive graph if and only if the original graph is also arc-transitive. In this paper, we generalize this notion to t-regular graphs Γ  and replace each vertex with a complete graph Kt on t vertices. We determine necessary and sufficient conditions for T(Γ) to be hamiltonian, show Aut(T(Γ)) ≅ Aut(Γ), as well as show that if Γ  is vertex-transitive, then T(Γ ) is vertex-transitive if and only if Γ  is arc-transitive. Finally, in the case where t is prime we determine necessary and sufficient conditions for T(Γ) to be isomorphic to a Cayley graph as well as an additional necessary and sufficient condition for T(Γ) to be vertex-transitive.


Truncation, automorphism group, Cayley graph, Hamiltonian.

Full Text:


DOI: https://doi.org/10.26493/1855-3974.665.4b6

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