Reachability relations in digraphs (Q942126): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:41, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reachability relations in digraphs |
scientific article |
Statements
Reachability relations in digraphs (English)
0 references
4 September 2008
0 references
This paper studies a family of reachability relations defined on the vertex set of a digraph. First, the weight of a walk is defined to be 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. It is shown that the interplay of certain properties of digraph such as having property Z, number of ends, growth conditions, and vertex degree is strongly related to the properties of the two sequences of equivalence relations. It gives two necessary and sufficient conditions for a connected infinite locally finite transitive digraph to have property Z in terms of properties of the two sequences, one for two-ended digraphs and one for digraphs with infinitely many ends. It is also shown that if at least one of these two sequences of equivalence relations is infinite, for some connected infinite locally finite transitive digraphs, the digraph in question must have exponential growth.
0 references
reachability
0 references
equivalence relation
0 references
transitive digraph
0 references