Directed Cycles with Two Chords and Strong Spanning Directed Subgraphs with Few Arcs

✍ Scribed by Carsten Thomassen

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 314 KB
• Volume: 66
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1996.0003

✦ Synopsis

We prove the conjecture of D. A. Marcus (1981) that every strongly 2-arcconnected directed graph has a directed cycle with at least two chords. As a consequence, every strongly 2-arc-connected directed graph with m arcs has a spanning strong directed subgraph with less than 2 3 m arcs. The constant 2 3 is best possible.

1996 Academic Press, Inc. 1. Introduction Marcus [2] investigated for which nonnegative real numbers a, b the following holds: If D is a strongly 2-arc-connected digraph (directed graph) with n vertices and m arcs, then D has a strong spanning subdigraph with at most am+b(n&1) arcs. He solved the problem except for the pairs (a, b) in the trapezoid with corners [ 2 3 , 0], [ 7 10 , 0], [ 3 10 , 4 5 ], [ 1 3 , 2 3

]. He showed that in order to dispose of that trapezoid it suffices to prove his conjecture that the pair (a, b)=[ 1 3 , 2 3 ] satisfies the above assertion. He also showed that this would follow from his conjecture that every strongly 2-arc-connected digraph has a directed cycle with at least two arcs. That conjecture is also mentioned in [1, p. 32] and [3, p. 166]. We shall here prove the conjecture.

Marcus' argument [2] for the consequence that every 2-arc-connected digraph D with n vertices and m arcs has a strong spanning subdigraph with at most 1 3 m+ 2 3 (n&1) arcs is simple: We just contract a dicycle (with c chords, c 2, and say p vertices) into a single vertex and apply the induction hypothesis to the resulting 2-arc-connected digraph, which then contains a strong spanning subdigraph D$ with at most 1 3 (m&p&c)+ 2 3 (n&p) arcs. Adding C to D$ gives a strong spanning subdigraph of D with 1 3 (m&p&c)+ 2 3 (n&p)+p 1 3 m+ 2 3 (n&1) arcs.

article no. 0003 24 0095-8956Â96 12.00