Reachability relations in digraphs

Abstract: In this paper we study reachability relations on vertices of digraphs, informally defined as follows. First, the weight of a walk is equal to the number of edges traversed in the direction coinciding with their orientation, minus the number of edges traversed in the direction opposite to their orientation. Then, a vertex is -related to a vertex if there exists a 0-weighted walk from to whose every subwalk starting at has weight in the interval . Similarly, a vertex is -related to a vertex if there exists a 0-weighted walk from to whose every subwalk starting at has weight in the interval . For all positive integers , the relations and are equivalence relations on the vertex set of a given digraph. We prove that, for transitive digraphs, properties of these relations are closely related to other properties such as having property , the number of ends, growth conditions, and vertex degree. [Copyright &y& Elsevier]