Reachability relations in digraphs

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

ENG

Prijava

Prva stran / Izpis gradiva

Izpis gradiva

A- | A+ | Natisni

Naslov:	Reachability relations in digraphs
Avtorji:	ID Malnič, Aleksander (Avtor) ID Marušič, Dragan (Avtor) ID Seifter, Norbert (Avtor) ID Šparl, Primož (Avtor) ID Zgrablić, Boris (Avtor)
Datoteke:	http://dx.doi.org/10.1016/j.ejc.2007.11.003
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	IAM - Inštitut Andrej Marušič
Opis:	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.
Ključne besede:	graph theory, digraph, reachability relations, end of a graph, property $\mathbb{Z}$ , growth
Leto izida:	2008
Št. strani:	str. 1566-1581
Številčenje:	Vol. 29, no. 7
PID:	20.500.12556/RUP-7717
ISSN:	0195-6698
UDK:	519.17
DOI:	10.1016/j.ejc.2007.11.003
COBISS.SI-ID:	2017509
Datum objave v RUP:	03.04.2017
Število ogledov:	3478
Število prenosov:	139
Metapodatki:
:	MALNIČ, Aleksander, MARUŠIČ, Dragan, SEIFTER, Norbert, ŠPARL, Primož in ZGRABLIĆ, Boris, 2008, Reachability relations in digraphs. [na spletu]. 2008. Vol. 29, no. 7, p. 1566–1581. [Dostopano 17 april 2025]. DOI 10.1016/j.ejc.2007.11.003. Pridobljeno s: http://dx.doi.org/10.1016/j.ejc.2007.11.003 Kopiraj citat