Strongly adjacency-transitive graphs and uniquely shift-transitive graphs (Q1349107): Difference between revisions

An adjacency automorphism \(\sigma\in\text{Aut}(\Gamma)\) of a finite, simple, undirected graph \(\Gamma\) has the property that \(d(x,\sigma(x))\leq 1\) holds for all \(x\in V(\Gamma)\). Call \(\Gamma\) strongly adjacency-transitive if for all \([x,y]\in E(\Gamma)\) there exists an adjacency automorphism sending \(x\) to \(y\). Given a group \(G\) acting on a set \(X\) and \(\emptyset\neq S=S^{-1}\subseteq G\), define the action graph \(\text{ActGrph}(G,X,S)\) to have vertex set \(X\) and edge set \(\{[x,y]:y=sx\neq x\;\text{for\;some} s\in S\}\). Theorem 2.2: \(\Gamma\) is strongly adjacency-transitive if and only if \(\Gamma\) is isomorphic to some \(\text{ActGrph}(G,X,S)\), where \(G\) acts transitively and faithfully on \(X\), \(S\) generates \(G\), and \(S\) is closed under both inverses and conjugation. A shift is an adjacency automorphism with no fixed point. \(\Gamma\) is strongly (resp. uniquely) shift-transitive if for each \([x,y]\in E(\Gamma)\) there exists at least one (resp., a unique) shift sending \(x\) to \(y\). Theorem 3.1: \(\Gamma\) is uniquely shift-transitive if and only if in the prime Cartesian factorization of \(\Gamma\), all factors are uniquely shift-transitive and at most one factor is isomorphic to \(K_2\). The authors acknowledge a similar result due to \textit{B. Larose, F. Laviolette}, and \textit{C. Tardif} [Eur. J. Comb. 19, No. 7, 867-881 (1998; Zbl 0916.05032)]. The article concludes with two questions. 1. Is every uniquely shift-transitive Cayley graph a Cayley graph of an abelian group? 2. Does there exist a uniquely shift-transitive non-Cayley graph? The answer is affirmative if ``uniquely'' is weakened to ``strongly''.