Bounds of the longest directed cycle length for minimal strong digraphs (Q1106239)

The subjects of the paper are directed cycles in minimal strong digraphs. A digraph D is called strong if it contains a directed (u,v)-path for any ordered set of vertices (u,v). If D is strong and D-e is no longer strong for any arc e in D, it is called a minimal strong digraph. Let \(\nu\) (D) denote the cyclomatic number of D. First it is shown that a minimal strong digraph D has \(\nu\) (D) directed cycles such that every arc of D is contained in at least one of them. A reducible chain is defined to be a directed path \(w=(x,v_ 1,...,v_ k,y)\), \(k\geq 1\) in a strong digraph D where both indegree and outdegree of each vertex \(v_ i\) are equal to one and \(D-\{v_ 1,...,v_ k\}\) remains to be strong. The authors prove that any minimal strong digraph D with cyclomatic number \(\nu\) (D)\(\geq 2\) has at least two reducible chains. Futhermore, if C is a longest directed cycle of D, D has a reducible chain w which is arc-disjoint with C. Using these results the main theorem of the paper is proved. It gives the following sharp lower and upper bounds on length \(\ell (D)\) of the longest directed cycle in a nontrivial minimal strong digraph D \(\lceil m/(m-n+1)\rceil \leq \ell (D)\leq 2n-m\), where n and m are the number of nodes and arcs in D respectively. Finally it is mentioned (without proof) that an analogous result \(\lceil 2m/(m-n+2)\rceil \leq \ell (G)\leq 2n-m\) can be derived for minimal 2-edge connected graphs G (without cut vertices).