3
$\begingroup$

Is anything known about the number of minimal strongly connected digraphs on $n$ labeled nodes? (``Minimal’’ meaning that on the deletion of any arc, strong connectivity is lost.) Some values are given in sequence A130768 at OEIS.org, but no generating function or asymptotic estimate is given. This feels like something that should be known, being a natural digraph analog of the famous question of the number of trees on $n$ labeled vertices.

Context: I’m preparing lectures, and while I was writing notes on a theorem of the form “the following 5 statements are equivalent”, it occurred to me that it would be nice to discuss in class the question: “in how many ways can one show that $n$ statements are equivalent, without any redundant implications in the proof?”.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.