Seifter, Norbert; Trofimov, Vladimir I. Reachability relations and the structure of transitive digraphs. (English) Zbl 1178.05051 Electron. J. Comb. 16, No. 1, Research Paper R26, 18 p. (2009). Summary: 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. Cited in 2 Documents MSC: 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C20 Directed graphs (digraphs), tournaments PDFBibTeX XMLCite \textit{N. Seifter} and \textit{V. I. Trofimov}, Electron. J. Comb. 16, No. 1, Research Paper R26, 18 p. (2009; Zbl 1178.05051) Full Text: EuDML EMIS