## Date of Award

8-19-2024

## Document Type

Open Access Dissertation

## Department

Mathematics

## First Advisor

Joshua Cooper

## Abstract

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.

## Rights

© 2024, Gabrielle Anne Tauscheck

## Recommended Citation

Tauscheck, G. A.(2024). *Generalizations of the Graham-Pollak Tree Theorem.* (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/7811