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

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
 
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(01)00096-6 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2158221582 / rank
 
Normal rank

Latest revision as of 08:40, 30 July 2024

scientific article
Language Label Description Also known as
English
Strongly adjacency-transitive graphs and uniquely shift-transitive graphs
scientific article

    Statements

    Strongly adjacency-transitive graphs and uniquely shift-transitive graphs (English)
    0 references
    0 references
    0 references
    0 references
    21 May 2002
    0 references
    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''.
    0 references
    vertex-transitive graph
    0 references
    Cayley graph
    0 references
    shift
    0 references
    action graph
    0 references
    adjacency automorphism
    0 references

    Identifiers