Infinite primitive directed graphs (Q2269533)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Infinite primitive directed graphs
scientific article

    Statements

    Infinite primitive directed graphs (English)
    0 references
    0 references
    17 March 2010
    0 references
    Let \(\Gamma\) be a graph or digraph with vertex set \(V\), and let \(G=\text{Aut}\,\Gamma\) be its automorphism group. The (di)graph \(\Gamma\) is \textit{vertex-transitive} if \(G\) acts transitively on \(V\); it is \textit{automorphism-regular} if \(G\) acts regularly on \(V\); and it is \textit{primitive} if \(G\) is a primitive permutation group on \(V\) (that is, \(V\) does not contain a non-trivial block). Let \(\Gamma\) be an infinite (di)graph with connectivity one. A \textit{lobe} of \(\Gamma\) is a connected sub(di)graph of \(\Gamma\) that is maximal subject to the condition that it has connectivity \(\geq 2\). \textit{H.\,A. Jung} and \textit{M.\,E. Watkins} [``On the structure of infinite vertex-transitive graphs,'' Discrete Math. 18, 45-53 (1977; Zbl 0357.05050)] characterized the vertex-transitive primitive graphs with connectivity one as those whose lobes are primitive, pairwise isomorphic and each has at least three vertices. The author shows an analogous result for digraphs: If \(\Gamma\) is a vertex-transitive digraph with connectivity one, then it is primitive if and only if the lobes of \(\Gamma\) are primitive but not automorphism-regular, pairwise isomorphic and each has at lest three vertices. Moreover, the author characterizes the counterexamples to the unmodified extension of the result of Jung and Watkins: If \(\Gamma\) is a vertex-transitive imprimitive digraph with connectivity one, then the associated (undirected) graph is primitive if and only if the lobes of \(\Gamma\) are pairwise isomorphic directed \(p\)-cycles, for some odd prime \(p\).
    0 references
    primitive
    0 references
    graph
    0 references
    digraph
    0 references
    permutation
    0 references
    group
    0 references
    orbital graph
    0 references
    orbital digraph
    0 references
    block-cut-vertex tree
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references