Abstract
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 σ 1 , σ 2 ,…,σ k ∈ Aut (Γ) such that σ 1 σ 2 …σ 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.
Similar content being viewed by others
References
Hammack R, Imrich W, Klavžar S (2011) Handbook of product graphs. Crc Press, New York
Larose B, Laviolette F, Tardif C (1998) On normal Cayley graphs and homidempotent of graphs. Eur J Combin 19:867–881
Pisanski T, Tucker TW, Zgrablić B (2002) Strongly adjacency-transitive graphs and uniquely shift-transitive graphs. Discret Math. 244:389–398
Verret G (2009) Shifts in Cayley graphs. Discret Math 309:3748–3756
Weichsel PM (1962) The Kronecker product of graphs. Proc Am Math Soc 13:47–52
Wielandt H (1966) Permutation groups. Academic Press, New York
Zgrablić B (1998) On adjacency-transitive graphs. Discret Math 182:321–332
Zgrablić B (2000) A note on adjacency-transitivity of a graph and its complement. Graphs Combin 16:463–465
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sharifi, S., Iranmanesh, M.A. Adjacency and Shift-Transitivity in Graph Products. Iran J Sci Technol Trans Sci 41, 707–711 (2017). https://doi.org/10.1007/s40995-017-0283-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40995-017-0283-0