Strongly adjacency-transitive graphs and uniquely shift-transitive graphs Original Research Article

An automorphism σ of a finite simple graph Γ is an adjacency automorphism if for every vertex x∈V(Γ), either σx=x or σx is adjacent to x in Γ. An adjacency automorphism fixing no vertices is a shift. A connected graph Γ is strongly adjacency-transitive (respectively, uniquely shift-transitive) if there is, for every pair of adjacent vertices x,y∈V(Γ), an adjacency automorphism (respectively, a unique shift) σ∈Aut Γ sending x to y. The action graph Γ=ActGrph(G,X,S) of a group G acting on a set X, relative to an inverse-closed nonempty subset S⊆G, is defined as follows: the vertex-set of Γ is X, and two different vertices x,y∈V(Γ) are adjacent in Γ if and only if y=sx for some s∈S. A characterization of strongly adjacency-transitive graphs in terms of action graphs is given. A necessary and sufficient condition for cartesian products of graphs to be uniquely shift-transitive is proposed, and two questions concerning uniquely shift-transitive graphs are raised.