Name
Abstract | ||
|---|---|---|
In this paper we investigate reachability relations on the vertices of digraphs. If W is a walk in a digraph D, then the height of W is equal to the number of edges traversed in the direction coinciding with their orientation, minus the number of edges traversed opposite to their orientation. Two vertices u; v is an element of V (D) are R(a,b) = related if there exists a walk of height 0 between u and v such that the height of every subwalk of W, starting at u, is contained in the interval [a, b], where a ia a non-positive integer or a = -infinity and b is a non-negative integer or b = infinity. Of course the relations R(a,b) are equivalence relations on V(D). Factorising digraphs by R(a,infinity) and R(-infinity,b), respectively, we can only obtain a few different digraphs. Depending upon these factor graphs with respect to R(-infinity,b) and R(a,infinity) it is possible to de fine five different "basic relation-properties" for R(-infinity,b) and R(a,infinity), respectively. Besides proving general properties of the relations R(a,b), we investigate the question which of the "basic relation-properties" with respect to R(-infinity,b) and R(a,infinity) can occur simultaneously in locally finite connected transitive digraphs. Furthermore we investigate these properties for some particular subclasses of locally finite connected transitive digraphs such as Cayley digraphs, digraphs with one, with two or with in finitely many ends, digraphs containing or not containing certain directed subtrees, and highly arc transitive digraphs. |
Year | Venue | Keywords |
|---|---|---|
2009 | ELECTRONIC JOURNAL OF COMBINATORICS | equivalence relation,factor graph |
Field | DocType | Volume |
Integer,Discrete mathematics,Equivalence relation,Combinatorics,Vertex (geometry),Reachability,Cayley digraphs,Mathematics,Digraph,Transitive relation | Journal | 16.0 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 5 |
PageRank | References | Authors |
0.63 | 10 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| N Seifter | 1 | 137 | 26.49 |
| Vladimir I. Tromo | 2 | 5 | 0.63 |