Susan Gardner Mayhorn

"Construction of Minimally Strongly Connected Digraphs"

Abstract:

Possible methods for constructing minimally strongly connected digraphs (MSD's) are studied, and one method is implemented. A digraph D is an MSD if and only if D is strongly connected, but for every edge e the result of deleting it, D - e, is not strongly connected. An (n,m)-MSD is one with n vertices and m edges.

The algorithm implemented is a form of exhaustive search through all subdigraphs of MSD's. This search is made practical by using Brendan D. McKay's software package nauty to avoid exploring isomorphic duplicates. All nonisomorphic MSD's through 9 vertices were generated, and the numbers of labeled and unlabeled (n,m)-MSD's are reported for n up to 9. To obtain the numbers of labeled MSD's nauty was used to calculate the order of the automorphism group of each unlabeled MSD generated.

Possible alternative approaches to constructing MSD's are also discussed. These are based on Cunningham's X-join (substitution) digraph decomposition, Hedetniemi's characterizations of MSD's, Luce's decomposition theorems, and Grotschel's ear-decomposition characterization of minimal strong blocks.