MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G=(V,E)$ be a undirected simple graph, and $\Omega(G)$ denote the set of spanning trees of G. Does the next funcion $$l(G) = \min_{T \in \Omega(G)}\quad \sum_{uv \in E} \mbox{dist}_T(u,v)$$ have a specific name? Or has it been studied before?.

The problem is NP-hard, but I'm particularly interested in lower bounds of $l(G)$. Both for general graphs and for specific topologies.

share|cite|improve this question
I think this problem is exactly the same as the one here. – user2033412 Aug 17 '13 at 14:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.