Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Infinite primitive directed graphs - MaRDI portal

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