Locally-finite connected-homogeneous digraphs
(Citations: 3)
A digraph is connected-homogeneous if any isomorphism between finite
connected induced subdigraphs extends to an automorphism of the digraph. We
consider locally-finite connected-homogeneous digraphs with more than one end.
In the case that the digraph embeds a triangle we give a complete
classification, obtaining a family of tree-like graphs constructed by gluing
together directed triangles. In the triangle-free case we show that these
digraphs are highly arc-transitive. We give a classification in the two-ended
case, showing that all examples arise from a simple construction given by
gluing along a directed line copies of some fixed finite directed complete
bipartite graph. When the digraph has infinitely many ends we show that the
descendants of a vertex form a tree, and the reachability graph (which is one
of the basic building blocks of the digraph) is one of: an even cycle, a
complete bipartite graph, the complement of a perfect matching, or an infinite
semiregular tree. We give examples showing that each of these possibilities is
realised as the reachability graph of some connected-homogeneous digraph, and
in the process we obtain a new family of highly arc-transitive digraphs without
property Z.