Half-Transitive Graphs of Prime-Cube Order

    loading  Checking for direct PDF access through Ovid


We call an undirected graph X half-transitive if the automorphism group Aut X of X acts transitively on the vertex set and edge set but not on the set of ordered pairs of adjacent vertices of X. In this paper we determine all half-transitive graphs of order p3 and degree 4, where p is an odd prime; namely, we prove that all such graphs are Cayley graphs on the non-Abelian group of order p3 and exponent p2, and up to isomorphism there are exactly (p − 1)/2 such graphs. As a byproduct, this proves the uniqueness of Holt's half-transitive graph with 27 vertices.

    loading  Loading Related Articles