On Vosperian and Superconnected Vertex-Transitive Digraphs

Abstract

We investigate the structure of a digraph having a transitive automorphism group where every cutset of minimal cardinality consists of all successors or all predecessors of some vertex. We give a complete characterization of vosperian arc-transitive digraphs. It states that an arc-transitive strongly connected digraph is vosperian if and only if it is irreducible. In particular, this is the case if the degree is coprime with the order of the digraph. We give also a complete characterization of vosperian Cayley digraphs and a complete characterization of irreducible superconnected Cayley digraphs. These two last characterizations extend the corresponding ones in Abelian Cayley digraphs and the ones in the undirected case.

Research supported by the Ministry of Science and Innovation, Spain under project MTM2008-06620-C03-01/MTM and the Catalan Research Council under project 2009SGR01387. Research done when the last author was visiting Université Pierre et Marie Curie, E. Combinatoire, Paris, supported by the Ministry of Science and Innovation, Spain under the National Mobility Programme of Human Resources, Spanish National Programme I-D-I 2008–2011.