On automorphism groups of graph truncations - Alspach, Brian (Ars mathematica contemporanea, 2015)
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 ?$K_t$? on ?$t$? vertices. We determine necessary and sufficient conditions for ?$\mathscr{T}(Γ)$? to be hamiltonian, show ?$\text{Aut}(\mathscr{T}(Γ)) \cong \text{Aut}(Γ)$?, as well as show that if ?$Γ$? is vertex-transitive, then ?$\mathscr{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 ?$\mathscr{T}(Γ)$? to be isomorphic to a Cayley graph as well as an additional necessary and sufficient condition for ?$\mathscr{T}(Γ)$? to be vertex-transitive.
Keywords: automorphism group; Cayley graph; Cayleyjev graf; grupa avtomorfizmov; Hamiltonian; Hamiltonov graf; prisekanje; skoraj-uniformne družine delnih vsot; truncation