|
|
|
|
|
Given a weighted Graph, let W1, W2, W3, ... denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of weight W1 is at most k-1 edge swaps away from some spanning tree of weight Wk. Three other conjectures posed by Kano are proven for two special classes of graphs. Finally, we consider the algorithmic complexity of generating a spanning tree of weight Wk.