2
$\begingroup$

This question is not theoretical, it's about combinatorial meaning.

In graph theory there is a notion of complexity of a graph, which is equal to the number of spanning trees in a graph, which combinatorically simply means how much the graph is 'connected' (it is the way I understand it, is there any other combinatorial meaning? (there are different meanings of 'connectivity', including algebraic connectivity, which is second eigenvalue of Laplacian, but this one is more intuitive, as I think)). There is a fast algorithms to compute complexity of a given graph (look here for the discussion).

There is also a fast algorithm to compute the number of minimal spanning trees(MST) of a given weighted graph (for more information read this paper).

The question is: what does having several MST's mean in terms of graph and distances?

P.S. It certainly means that not all distances are different, but, maybe there is some property, which provides more interesting consequences?

Thank you!

$\endgroup$
  • $\begingroup$ You can use different MST as base of some approximation and heuristics, and if we have many of them our chance is better to get closer to the optimal solution, also I think if graph has many MST, means diameter in some subgraphs of original one should not be too large. $\endgroup$ – Saeed May 24 '13 at 13:31
  • $\begingroup$ It might be better to consider spanning forests rather than spanning trees if the aim is a combinatorial meaning. Spanning forests lead naturally to a hereditary associated property. $\endgroup$ – András Salamon Jun 25 '13 at 1:47

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.