On automorphism groups of graph truncations

Alspach, Brian ; Dobson, Edward

ARS MATHEMATICA CONTEMPORANEA, Tome 9 (2014), / Harvested from ARS MATHEMATICA CONTEMPORANEA

Résumé

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.

Détail

Publié le : 2014-01-01
DOI : https://doi.org/10.26493/1855-3974.665.4b6