Reachability relations in digraphsSeifter, Norbert (Avtor) Zgrablić, Boris (Avtor) Malnič, Aleksander (Avtor) Šparl, Primož (Avtor) Marušič, Dragan (Avtor) graph theorydigraphreachability relationsend of a graphproperty ▫\$\mathbb{Z}\$▫growthIn 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.20082016-04-08 16:46:15Delo ni kategorizirano7717ISSN: 0195-6698UDK: 519.17OceCobissID: 25427968COBISS_ID: 2017509DOI: 10.1016/j.ejc.2007.11.003sl