Spanning Trees Minimizing Geometric Indices¶

John C. Bowers (JMU faculty), Bradley McCoy (JMU faculty), Dema Nasrawt (student), and Aidan Pawlak (student)
33^rd Annual Fall Workshop on Computational Geometry · Nov 13, 2026 To appear

JMU faculty highlighted in purple; student co-authors in gold.

Abstract¶

A topological index assigns a number to a graph, treating every edge as having unit length. Motivated by the work of Abu-Affash et al. on a geometric analogue of the Wiener index, we study geometric versions of two indices: the mean subtree order and the Hosoya index. Given \(n\) points, the goal is a spanning tree minimizing the index. For the mean subtree order on a line, the sorted path is a tight \(2\)-approximation. In the plane, deciding whether there exists a spanning tree with mean subtree order at most \(\mu_0\) is NP-hard. For the Hosoya index, the optimal star gives an aspect-ratio-sensitive approximation, and it is weakly NP-hard to decide whether a spanning tree has Euclidean Hosoya index at most \(Z_0\) and total Euclidean length at most \(L_0\).

BibTeX¶

@misc{bowers2026spanning,
  author = {John C. Bowers and Bradley McCoy and Dema Nasrawt and Aidan Pawlak},
  title = {{Spanning Trees Minimizing Geometric Indices}},
  howpublished = {33rd Annual Fall Workshop on Computational Geometry},
  year = {2026},
  note = {To appear}
}

← All publications