On Vosperian and Superconnected Vertex-Transitive Digraphs

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.     

Vosperian and superconnected Abelian Cayley digraphs

A digraphX is said to be Vosperian if any fragment has cardinality either 1 or|V(X)| – d ⁺ (X) – 1.A digraph is said to be superconnected if every minimum cutset is the set of vertices adjacent from or to some vertex.In this paper we characterize Vosperian and superconnected Abelian Cayley directed graphs. Our main tool is a difficult theorem of J.H. Kemperman from Additive Group Theory.In particular we characterize Vosperian and superconnected loops network (also called circulants).     

On Subsets with Small Product in Torsion-Free Groups

G be a nonabelian torsion-free group. Let C be a finite generating subset of G such that . We prove that, for all subsets B of G with , we have . In particular, a finite subset X with cardinality satisfies the inequality if and only if there are elements , such that the following two conditions hold: (i) . (ii) where . Received: October 13, 1997/Revised: Revised August 18, 1998     

On multiply critically h-connected graphs

A conjecture of Slater states that K_{h + 1} is the unique k-critically h-connected noncomplete graph for 2k > h. We prove here that there is no k-critically h-connected connected graph with order $\text{?h + k ? 2}\text{for}\text{2k > h + 1}$. We prove also that there is no k-critically h-connected line graph for 2k > h. The last result was conjectured by Maurer and Slater. We apply in our proofs a method introduced by Mader.     

Two inverse results

Let A be a finite subset of a group G ₀ with |A ^?1 A|≤2|A?2. We show that there are an element α∈A and a non-null proper subgroup H of G such that one of the following holds:

• x ^?1 Hy?A ^?1 A, for all x,y∈A not both in Hα
• x Hy ^?1?AA ^?1, for all x,y∈A not both in αH

where G is the subgroup generated by A ^?1 A. Assuming that A ^?1 A≠G and that $\left| {A^{ - 1} A} \right| < \tfrac{{5|A|}} {3} $ , we show that there are a normal subgroup K of G and a subgroup H with K?H?A ^?1 A and 2|K|≥|H| such that $A^{ - 1} AK = KA^{ - 1} A = A^{ - 1} Aand6|K| \geqslant |A^{ - 1} A| = 3|H|$ .