Reachability relations, transitive digraphs and groups

Aleksander Malnič, Primož Potočnik, Norbert Seifter, Primož Šparl


In A. Malnič, D. Marušič, N. Seifter, P. Šparl and B. Zgrablič, Reachability relations in digraphs, Europ. J. Combin. 29 (2008), 1566–1581, it was shown that properties of digraphs such as growth, property Z, and number of ends are reflected by the properties of certain reachability relations defined on the vertices of the corresponding digraphs.
In this paper we study these relations in connection with certain properties of automorphism groups of transitive digraphs. In particular, one of the main results shows that if a transitive digraph admits a nilpotent subgroup of automorphisms with finitely many orbits, then its nilpotency class and the number of orbits are closely related to particular properties of reachability relations defined on the digraphs in question.
The obtained results have interesting implications for Cayley digraphs of certain types of groups such as torsion-free groups of polynomial growth.



Cayley digraph, reachability relation

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications