平衡半传递有向图的弧连通性

摘要

The digraph D=(V, E) is said to be maximally arc-connected, ifλ(D)=δ(D). Moreover, the digraph D is said to be super arc-connected, if every minimum arc cut of D is the set of the in-arcs or the out-arcs of some vertex of D. A bipartite digraph D with bipartition X1 and X2 is half-transitive if Aut(D) acts transitively on X1 and X2, respectively. In this paper, we prove that each strongly connected half-transitive digraph is maximally arc-connected. Moreover, we prove that for all but a few exceptions, the connected half-transitive balanced digraph is super arc-connected.%有向图D=(V, E)被称为是极大弧连通的,如果λ(D)=δ(D)。此外,有向图D被称为是超弧连通的,如果每个最小的弧割都是其某个点的入弧集或者出弧集。以X1和X2为两部的一个有向二部图是半传递的,如果自同构群Aut(D)分别传递的作用在X1和X2上。在这篇论文中,证明了强连通的半传递有向图是极大弧连通的。还证明了除了少部分例外,连通半传递平衡有向图是超弧连通的。