Infinite primitive directed graphs

Smith, Simon M.

Journal of Algebraic Combinatorics, Tome 31 (2010) no. 1, pp. 131-141.

Résumé

Summary: A group $G$ of permutations of a set $\Omega $is $primitive$ if it acts transitively on $\Omega $, and the only $G$-invariant equivalence relations on $\Omega $are the trivial and universal relations. A digraph $\Gamma $is $primitive$ if its automorphism group acts primitively on its vertex set, and is $infinite$ if its vertex set is infinite. It has connectivity one if it is connected and there exists a vertex $\alpha $ of $\Gamma $, such that the induced digraph $\Gamma \setminus { \alpha }$ is not connected. If $\Gamma $has connectivity one, a $lobe$ of $\Gamma $is a connected subgraph that is maximal subject to the condition that it does not have connectivity one. Primitive graphs (and thus digraphs) with connectivity one are necessarily infinite.

Détail

Keywords: keywords primitive, graph, digraph, permutation, group, orbital graph, orbital digraph, block-cut-vertex tree