Reachability relations in digraphs (Q942126): Difference between revisions

This paper studies a family of reachability relations defined on the vertex set of a digraph. First, the weight of a walk is defined to be 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. It is shown that the interplay of certain properties of digraph such as having property Z, number of ends, growth conditions, and vertex degree is strongly related to the properties of the two sequences of equivalence relations. It gives two necessary and sufficient conditions for a connected infinite locally finite transitive digraph to have property Z in terms of properties of the two sequences, one for two-ended digraphs and one for digraphs with infinitely many ends. It is also shown that if at least one of these two sequences of equivalence relations is infinite, for some connected infinite locally finite transitive digraphs, the digraph in question must have exponential growth.