Kiran Kumar Bhogadi

"Decomposition and Generation of Minimal Strongly Connected Digraphs"

Abstract:

A new algorithm for the generation of minimal strongly connected digraphs (MSDs) is implemented. The previous method – implemented by Susan Gardner Mayhorn – is practical for generating all MSDs through 9 vertices. Using the new method, we are able to generate all MSDs through 12 vertices and those that are 2-connected through 13 vertices, and to count the classes of digraphs by number of vertices and number of arcs, labeled and unlabeled. Our method uses Brendan D. McKay’s software package nauty in essential ways, to avoid counting duplicates and to calculate automorphism group orders for the labeled counting. Using MAPLE, we calculated the number of labeled MSDs on 13 vertices by number of arcs using an identity relating the number of labeled MSDs to those that are 2-connected, and the same identity provides a check on the numbers generated through 12 vertices.

In addition, a characterization of Cunningham’s decomposition trees for MSDs under the X-join (substitution) composition is given. The initial plan was to generate the MSDs using Cunningham’s decomposition theorem, which implies that any non-trivial MSD has a unique minimal decomposition in which each member is either a prime, a distar or a cycle. This approach was abandoned due to the difficulty of recognizing MSDs which are prime with respect to X-joins. Using our characterization, all the Cunningham prime MSDs through 11 vertices have been generated.