Publikace na Matematicko-fyzikální fakulta |
2015
Abstrakt
Two problems of Cameron, Praeger, and Wormald [Infinite highly arc transitive digraphs and universal covering digraphs, Combinatorica (1993)] are resolved. First, locally finite highly arc-transitive digraphs with universal reachability relation are presented.
Second, constructions of two-ended highly arc-transitive digraphs are provided, where each 'build- ing block' is a finite bipartite digraph that is not a disjoint union of complete bipartite digraphs. Both of these were conjectured impossible in the above-mentioned paper.
We also describe the structure of two-ended highly arc-transitive digraphs in more generality, heading towards a characterization of such digraphs. However, the complete characteriza- tion remains elusive.