Abstract
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.
Original language | American English |
---|---|
Journal | Theory and Applications of Graphs |
DOIs | |
State | Published - Jan 1 2016 |
Disciplines
- Discrete Mathematics and Combinatorics
Keywords
- Spanning tree
- edge-swap
- heuristic