  The quadratic minimum spanning tree problem (QMSTP) is the problem of finding
a spanning tree of a graph such that the total interaction cost between pairs
of edges in the tree is minimized. We first show that most of the bounding
approaches for the QMSTP are closely related. Then, we exploit an extended
formulation for the minimum spanning tree problem to derive a sequence of
relaxations for the QMSTP with increasing complexity. The resulting relaxations
differ from the relaxations in the literature. Namely, our relaxations have a
polynomial number of constraints and can be efficiently solved by a cutting
plane algorithm. Moreover our bounds outperform most of the bounds from the
literature.
