Reachability relations in digraphs

Malnič, Aleksander (avtor), Marušič, Dragan (avtor), Seifter, Norbert (avtor), Šparl, Primož (avtor), Zgrablić, Boris (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: graph theory, digraph, reachability relations, end of a graph, property ▫$\mathbb{Z}$▫, growth
• Vrsta gradiva: Delo ni kategorizirano
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: PEF - Pedagoška fakulteta
• Leto izida: 2008
• Št. strani: Str. 1566-1581
• Številčenje: Vol. 29, no. 7
• PID: 20.500.12556/RUL-45605
• UDK: 519.17
• ISSN pri članku: 0195-6698
• DOI: 10.1016/j.ejc.2007.11.003
• COBISS.SI-ID: 2017509
• Datum objave v RUL: 10.07.2015

Gradivo je del revije

• Naslov: European journal of combinatorics
• Skrajšan naslov: Eur. j. comb.
• Založnik: Elsevier
• ISSN: 0195-6698
• COBISS.SI-ID: 25427968

Sekundarni jezik

• Jezik: Angleški jezik
• Ključne besede: teorija grafov, usmerjeni grafi, rast