Descendants in highly arc transitive digraphs
type: Item
instance of: scholarly article
title: Descendants in highly arc transitive digraphs
zbMATH Open document ID: 0991.05054
DOI: 10.1016/S0012-365X(01)00171-6
author: Rögnvaldur G. Möller
published in: Discrete Mathematics
publication date: 2002-05-28T00:00:00Z
review text: A digraph \(D\) is said to be \(s\)-arc transitive if Aut\((D)\) acts transitively on the set of \(s\)-arcs. A highly arc transitive digraph is a digraph that is \(s\)-arc transitive for every \(s\geq 0\). A directed line \(L\) is a two way infinite sequence \(\ldots,v_{-1},v_0,v_1,v_2,\ldots\) such that \((v_i,v_{i+1})\) is an arc for all \(i\in{\mathbb{Z}}\). Denote by \(\text{desc}(L)\) the set of vertices in \(D\) that can be reached by a directed path from vertices in a directed line \(L\). The paper gives insight into the structure of the subdigraph spanned by \(\text{desc}(L)\). The main result is the following. Let \(D\) be a locally finite highly arc transitive digraph and let \(L\) be a directed line such that desc\((L)\) is the set of all vertices in \(D\). Then, there exist a directed tree \(T\) with in-valency 1 and finite out-valency, and an epimorphism \(\varphi\colon D\rightarrow T\) such that (i) \(\text{Aut}(D)\) acts on \(T\) by \(g(\varphi(v))=\varphi(g(v))\), and this action is highly arc transitive; and (ii) all the sets \(\varphi^{-1}(t)\), with \(t\) vertex in \(T\), have the same finite cardinality. Let \(v\) be a vertex in a transitive digraph \(D\) with finite out-valency. The number \(p_k\) of vertices \(u\) in \(D\) such that there is a directed path of length \(k\) from \(v\) to \(u\) does not depend on \(v\). The out-spread of \(D\) is defined as \(\limsup_{k\rightarrow\infty} (p_k)^{1/k}\). It is shown that the out-spread of a locally finite highly transitive digraph is an integer. Let \(Z\) be the digraph which has the set \({\mathbb{Z}}\) of integers as set of vertices and the couples \((i,i+1)\) with \(i\in{\mathbb{Z}}\) as set of arcs. In \textit{P. J. Cameron, C. E. Praeger} and \textit{N. C. Wormald} [Combinatorica 13, 377-396 (1993; Zbl 0793.05065)] it is shown that if a highly arc transitive digraph \(D\) has out-spread 1, then there exists an homomorphism \(\varphi\colon D\rightarrow Z\), and it is asked wheter \(\varphi^{-1}…
reviewed by: Josep M. Brunat
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1746234
zbMATH Keywords: highly arc transitive
zbMATH Keywords: digraph
zbMATH Keywords: automorphisms group
zbMATH Keywords: tree
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1746234