On the Maximum Degree of Minimum Spanning Trees

Motivated by practical VLSI applications, we study the maximum vertex degree in a minimum spanning tree (MST) under arbitrary LP metrics. We show that the maximum vertex degree in a maximum - degree LP MST equals the Hadwiger number of the corresponding unit ball. We then determine the maximum vertex degree in a minimum-degree LP MST; towards this end, we define the MST number, which is closely related to the Hadwiger number. We bound Hadwiger and MST numbers for arbitrary LP metrics, and focus on the L1 metric, where little was known. We show that the MST number of a diamond is 4, and that for the octahedron the Hadwiger number is 18 and the MST number is either 13 or 14. We also give an exponential lower bound on the MST number for an LP unit ball. Implications to LP minimum spanning trees and related problems are explored.
Note: Abstract extracted from PDF file via OCR

Robins, Gabriel, and Jeffrey Salowe. "On the Maximum Degree of Minimum Spanning Trees." University of Virginia Dept. of Computer Science Tech Report (1993).