Reachability relations in digraphs 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 ▫\$u\$▫ is ▫\$R_k^+\$▫-related to a vertex ▫\$v\$▫ if there exists a 0-weighted walk from ▫\$u\$▫ to ▫\$v\$▫ whose every subwalk starting at u has weight in the interval ▫\$[0,k]\$▫. Similarly, a vertex ▫\$u\$▫ is ▫\$R_k^-\$▫-related to a vertex ▫\$v\$▫ if there exists a 0-weighted walk from ▫\$u\$▫ to ▫\$v\$▫ whose every subwalk starting at ▫\$u\$▫ has weight in the interval ▫\$[-k,0]\$▫. For all positive integers ▫\$k\$▫, the relations ▫\$R_k^+\$▫ and ▫\$R_k^-\$▫ 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 ▫\$\mathbb{Z}\$▫, the number of ends, growth conditions, and vertex degree. 2008 2016-04-08 16:46:15 1033 graph theory, digraph, reachability relations, end of a graph, property ▫\$\mathbb{Z}\$▫, growth teorija grafov, usmerjeni grafi, rast r6 Norbert Seifter 70 Boris Zgrablić 70 Aleksander Malnič 70 Primož Šparl 70 Dragan Marušič 70 ISSN 2 0195-6698 UDK 4 519.17 OceCobissID 13 25427968 COBISS_ID 3 2017509 DOI 15 10.1016/j.ejc.2007.11.003 0 Predstavitvena datoteka 2016-04-08 16:46:16