Highly arc-transitive digraphs -- structure and counterexamples

DOI10.1007/S00493-014-3040-4MaRDI QIDQ1677569zbMATH OpenOpenAlexWikidataFDO

Authors Matt DeVos, Bojan Mohar, Robert Šámal

Publication date 10 November 2017

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-014-3040-4

automorphism groups ends of infinite graphs highly arc-transitive digraphs

Directed graphs (digraphs), tournaments (05C20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Infinite graphs (05C63)

Review text

Unlike the case of connected finite digraphs, where outside the oriented cycles the \(s\)-arc-transitivity is limited to \( s \leq 8 \), families of infinite digraphs which are \(s\)-arc-transitive for all \( s \geq 0 \) exist in abundance. Nevertheless, constructions of such families are often quite involved; with the proof of the \(s\)-arc-transitivity of the resulting graphs, for every \(s \geq 0 \), `encoded' in the construction from its very beginning. The existence of conjectures assuming various limits on the structure of these infinite digraphs is therefore not surprising, even though some of them are proven false with the introduction of new, more imaginative, constructions. This is what happens in the present article, which introduces a number of constructions leading to counterexamples to conjectures of this type. In their attempts to classify these highly symmetric infinite digraphs, called highly arc-transitive digraphs, mathematicians divide the families according to their number of ends or with regard to their reachability properties. Two arcs in an infinite digraph are said to be mutually reachable if there exists an orientation alternating path starting from one and ending in the other. In case of arc-transitive graphs, all components induced by the classes of the equivalence relation of reachability are isomorphic, and the non-existence of locally finite highly arc-transitive digraphs with a single equivalence class under the relation of reachability has been conjectured; based on a number of negative results for specific parameters. The conjecture is proved wrong via a construction of a single-reachability-class infinite locally finite highly arc-transitive digraph of an in- and out-degree \(d\) for every composite \( d \geq 4 \). Interestingly, these are all the degrees for which the non-existence of such graphs had not been previously proved. The rest of the paper is devoted to two-ended highly arc-transitive digraphs. If we let \(R(D)\) denote the digraph induced by a single reachability component of the digraph \(D\), another conjecture assumed the non-existence of connected highly arc-transitive digraphs admitting a homomorphism onto an infinite path with finite vertex pre-images for which \(R(D)\) does not form a complete bipartite digraph. This again is proved false via a number of constructions, and the situation is shown quite a bit more complicated. A general construction which yields all two-ended highly arc-transitive graphs is introduced; the construction however also produces digraphs which are not highly arc-transitive.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Highly arc-transitive digraphs -- structure and counterexamples

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1677569)