Finding spanning trees under various restrictions has been an interesting question to researchers. A "dense" tree, from a graph theoretical point of view, has small total distances between vertices and large number of substructures. In this note, the "density" of a spanning tree is conveniently measured by the weight of a tree (defined as the sum of products of adjacent vertex degrees). By utilizing established conditions and relations between trees with the minimum total distance or maximum number of sub-trees, an edge-swap heuristic for generating "dense" spanning trees is presented. Computational results are presented for randomly generated graphs and specific examples from applications.
Available at: http://works.bepress.com/hua_wang/130/