一类超欧拉有向图中的超欧拉bypass

On Supereulerian Bypasses in One Class of Supereulerian Digraph

设D是严格有向图(无环与重弧),λ(D)是有向图D的弧强连通度,α′(D)表示有向图D的匹配数.如果有向图D中含有一个生成欧拉子图反向一条弧的方向所得的子图,则称有向图D含有一个超欧拉bypass.证明了一个强连通有向图D满足λ(D)≥α′(D)≥5,则有向图D含有一个超欧拉bypass.

Let D be a digraph andλ(D)be the arc-strong connectivity of D,α′(D)be the size of a maximum matching of D.In this paper we show that if a strong digraph D andλ(D)≥α′(D)≥5,then D contains a supereulerian bypass(i.e.,a subdigraph is obtained from a spanning eulerian subdigraph by reversing exactly one arc).