= Circuit-cover bound by independence number
{title2=$\#\text{circuits}\le\alpha(D)$}
For a nontrivial <strongly connected directed graph>, a <coherent cyclic order of a digraph> and the <Dilworth theorem> produce a <spanning circuit family> with at most its <independence number> circuits. Put a largest consecutive stable block first and duplicate its vertices as sinks. Use forward edges and edges into the sink copies to form an acyclic auxiliary graph. Its reachability order has width equal to the block size. Expand a chain partition to paths, then exchange intersecting path suffixes until the permutation of source-to-sink labels has as many cycles as possible. Paths in the same permutation cycle are disjoint, so identifying copied endpoints produces simple directed circuits. A windmill of directed triangles sharing one vertex shows that the bound is sharp.
Back to article page
