I am wondering how to calculate the number of spanning arborescences in a directed graph when a root is specified. For example:

where there are 5 spanning arborescences. Note that there is an edge from b2 to b3 and one from b3 to b2.

Angela Pretorius mentioned a method in Number of Spanning Arborescences, Mathematics, but there is no euclidean circuit in this example. It seems that he/she is referring to BEST theorem.


1 Answer 1


It seems that Kirchhoff's theorem can be used:

Kirchhoff's theorem can be modified to count the number of oriented spanning trees in directed multigraphs. The matrix Q is constructed as follows:

The entry i, j for distinct i and j equals −m, where m is the number of edges from i to j;
The entry i, i equals the indegree of i minus the number of loops at i.

The number of oriented spanning trees rooted at a vertex i is the determinant of the matrix gotten by removing the i-th row and column of Q.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.