Generalizations of the Graham-Pollak Tree Theorem

Graham and Pollak showed in 1971 that the determinant of a tree’s distance matrix depends only on its number of vertices, and, in particular, it is always nonzero. This dissertation will generalize their result via two different directions: Steiner distance k-matrices and distance critical graphs. The Steiner distance of a collection of k vertices in a graph is the fewest number of edges in any connected subgraph containing those vertices; for k = 2, this reduces to the ordinary definition of graphical distance. Here, we show that the hyperdeterminant of the Steiner distance k-matrix is always zero if k is odd and nonzero if k is even, extending the result beyond k = 2. We conjecture that not just the vanishing, but the value itself, of the Steiner distance k-matrix hyperdeterminant of an n-vertex tree depends only on k and n. We further introduce new techniques to prove that the distance matrix (the k = 2 case) of a tree has a nonzero determinant, thus providing weaker versions of the Graham-Pollak Theorem. In the second half of the dissertation, we focus on distance critical graphs. In a tree, standard distance is measured by the unique path connecting two vertices. The distance measure, however, may be obtained from multiple paths if the graph is not a tree. A distance critical graph is a connected graph such that no vertex can be deleted without altering the distance metric on the remaining vertices. We generalize this unique path distance concept that holds within a tree by introducing and discussing properties of distance critical graphs.