ADJACENCY AND SHIFT-TRANSITIVITY IN GRAPH PRODUCTS

Document Type : Regular Paper

Author

Yazd University

Abstract

Let $Gamma$ be a finite simple graph with automorphism group $Aut(Gamma).$
An automorphism $sigma$ of $Gamma$ is said to be an adjacency automorphism, if for every vertex
$xin V(Gamma)$, either $sigma x=x$ or $sigma x$ is adjacent to
$x$ in $Gamma$. A shift is an adjacency automorphism fixing no vertices. The graph
$Gamma$ is (shift) adjacency-transitive if for every pair of vertices $x, x'in V(Gamma)$,
there exists a sequence of (shift) adjacency automorphisms $sigma_{1},sigma_{2},...sigma_{k}inAut(Gamma)$
such that $sigma_{1}sigma_{2}...sigma_{k}x=x'$. If, in addition, for every pair of
adjacent vertices $x, x'in V(Gamma)$ there exists an (shift) adjacency automorphism say
$sigmain Aut(Gamma)$ sending $x$ to $x'$, then $Gamma$ is strongly (shift) adjacency-transitive.
If for every pair of adjacent vertices $x, x'in V(Gamma)$ there exists exactly one shift $sigmainAut(Gamma)$
sending $x$ to $x'$, then $Gamma$ is uniquely shift-transitive. In this paper, we investigate these concepts in
some standard graph products.

Keywords

Main Subjects