Article ID Journal Published Year Pages File Type
4649284 Discrete Mathematics 2010 16 Pages PDF
Abstract

The descendant set desc(α) of a vertex αα in a directed graph (digraph) is the subdigraph on the set of vertices reachable by a directed path from αα. We investigate desc(α) in an infinite highly arc-transitive digraph DD with finite out-valency and whose automorphism group is vertex-primitive. We formulate three conditions which the subdigraph desc(α) must satisfy and show that a digraph ΓΓ satisfying our conditions is constructed in a particular way from a certain bipartite digraph ΣΣ, which we think of as its ‘building block’. In particular, ΓΓ has infinitely many ends. Moreover, we construct a family of infinite (imprimitive) highly arc-transitive digraphs whose descendant sets satisfy our conditions and are not trees.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,