Reachability relations in digraphs

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

SLO

First page / Show document

Show document

A- | A+ | Print

Title:	Reachability relations in digraphs
Authors:	ID Malnič, Aleksander (Author) ID Marušič, Dragan (Author) ID Seifter, Norbert (Author) ID Šparl, Primož (Author) ID Zgrablić, Boris (Author)
Files:	http://dx.doi.org/10.1016/j.ejc.2007.11.003
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	IAM - Andrej Marušič Institute
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 $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.
Keywords:	graph theory, digraph, reachability relations, end of a graph, property $\mathbb{Z}$ , growth
Year of publishing:	2008
Number of pages:	str. 1566-1581
Numbering:	Vol. 29, no. 7
PID:	20.500.12556/RUP-7717
ISSN:	0195-6698
UDC:	519.17
DOI:	10.1016/j.ejc.2007.11.003
COBISS.SI-ID:	2017509
Publication date in RUP:	03.04.2017
Views:	3436
Downloads:	139
Metadata:
:	MALNIČ, Aleksander, MARUŠIČ, Dragan, SEIFTER, Norbert, ŠPARL, Primož and ZGRABLIĆ, Boris, 2008, Reachability relations in digraphs. [online]. 2008. Vol. 29, no. 7, p. 1566–1581. [Accessed 2 April 2025]. DOI 10.1016/j.ejc.2007.11.003. Retrieved from: http://dx.doi.org/10.1016/j.ejc.2007.11.003 Copy citation