Adjacency and Shift-Transitivity in Graph Products

Let Γ be a finite simple graph with automorphism group Aut (Γ). An automorphism σ of Γ is said to be an adjacency automorphism, if for every vertex x ∈ V (Γ), either σx = x or σx is adjacent to x in Γ. A shift is an adjacency automorphism fixing no vertices. The graph Γ is (shift) adjacency-transitive if for every pair of vertices x, x′ ∈ V (Γ), there exists a sequence of (shift) adjacency automorphisms σ ₁ , σ ₂ ,…,σ _k ∈ Aut (Γ) such that σ ₁ σ ₂ …σ _k x = x′. If, in addition, for every pair of adjacent vertices x, x′ ∈ V (Γ) there exists an (shift) adjacency automorphism say σ ∈ Aut (Γ) sending x to x′, then Γ is strongly (shift) adjacency-transitive. If for every pair of adjacent vertices x, x′ ∈ V (Γ) there exists exactly one shift σ ∈ Aut (Γ) sending x to x′, then Γ is uniquely shift-transitive. In this paper, we investigate these concepts in some standard graph products.

Authors and Affiliations

1. Department of Mathematical Sciences, Yazd University, Yazd, 89195-741, Iran

   Sh. Sharifi & Mohammad A. Iranmanesh

Corresponding author

Correspondence to Mohammad A. Iranmanesh.

Reprints and permissions