Reachability Relations and the Structure of Transitive Digraphs

Norbert Seifter, Vladimir I. Trofimov

Abstract


In this paper we investigate reachability relations on the vertices of digraphs. If $W$ is a walk in a digraph $D$, then the height of $W$ is equal to the number of edges traversed in the direction coinciding with their orientation, minus the number of edges traversed opposite to their orientation. Two vertices $u,v\in V(D)$ are $R_{a,b}$-related if there exists a walk of height $0$ between $u$ and $v$ such that the height of every subwalk of $W$, starting at $u$, is contained in the interval $[a,b]$, where $a$ ia a non-positive integer or $a=-\infty$ and $b$ is a non-negative integer or $b=\infty$. Of course the relations $R_{a,b}$ are equivalence relations on $V(D)$. Factorising digraphs by $R_{a,\infty}$ and $R_{-\infty,b}$, respectively, we can only obtain a few different digraphs. Depending upon these factor graphs with respect to $R_{-\infty,b}$ and $R_{a,\infty}$ it is possible to define five different "basic relation-properties" for $R_{-\infty,b}$ and $R_{a,\infty}$, respectively.

Besides proving general properties of the relations $R_{a,b}$, we investigate the question which of the "basic relation-properties" with respect to $R_{-\infty,b}$ and $R_{a,\infty}$ can occur simultaneously in locally finite connected transitive digraphs. Furthermore we investigate these properties for some particular subclasses of locally finite connected transitive digraphs such as Cayley digraphs, digraphs with one, with two or with infinitely many ends, digraphs containing or not containing certain directed subtrees, and highly arc transitive digraphs.


Full Text: PDF