On the spanning trees of weighted graphs (Q1204524)

The paper deals with several natural questions that arise when the spanning trees of a weighted graph are partitioned into the weight classes. The authors prove that every minimum-weight spanning tree is at most \(k-1\) edge swaps away from some representative of the \(k\)-th weight class, thereby settling a conjecture of \textit{M. Kano} [Combinatorica 7, 205-214 (1987; Zbl 0624.05027)]. In this latter paper, three more conjectures were posed for which the authors propose a stronger unified conjecture and confirm it in two non-trivial special cases. Finally, they consider the algorithmic complexity of the problem of generating a representative of the \(k\)-th weight class.