摘要
:
In this paper we investigate reachability relations on the vertices of digraphs. IfW is a walk in a digraph D, then the height of W is equal to the number of edgestraversed in the direction coinciding with their orientation, minus...
展开
In this paper we investigate reachability relations on the vertices of digraphs. IfW is a walk in a digraph D, then the height of W is equal to the number of edgestraversed in the direction coinciding with their orientation, minus the number ofedges traversed opposite to their orientation. Two vertices u, v E V(D) are Ra,b-related if there exists a walk of height 0 between u and v such that the height ofevery subwalk of W, starting at u, is contained in the interval [a, b], where a is anon-positive integer or a = and b is a non-negative integer or b = no. Of coursethe relations Ra,b are equivalence relations on V (D). Factorising digraphs by Ra,and R,b, respectively, we can only obtain a few different digraphs. Dependingupon these factor graphs with respect to R,b and Ra, it is possible to definefive different "basic relation-properties for R,b and Ra,, respectively. Besides proving general properties of the relations Ra,b, we investigate the ques-tion which of the "basic relation-properties" with respect to R,b and Ra, canoccur simultaneously in locally finite connected transitive digraphs. Furthermorewe investigate these properties for some particular subclasses of locally finite con-nected transitive digraphs such as Cayley digraphs, digraphs with one, with two orwith infinitely many ends, digraphs containing or not containing certain directedsubtrees, and highly arc transitive digraphs.
收起