Preprint announcement: 'Distance Exceptional Graphs and the Curvature Index'
by Sawyer
Back in February, myself and a couple fellow graduate students at UCSD took part in the fourth-annual Math-a-thon workshop organized by the Mathematics Graduate Student Council over President’s Day weekend. We decided to investigate a unique problem of Steinerberger, described below, which since 2023 has seen some interesting progress but for which deeper understanding remained elusive. During our search we uncovered a graph invariant which seems to shed a decent amount of light on what’s going on. As as result I am excited to report that we have a preprint out this week based on the effort!
The paper can be found on ArXiv.
A graph $G=(V,E)$ on $n$ vertices is said to be \emph{distance exceptional} if the equation $D\vec{x} = \vec{1}$ admits no solution $\vec{x}\in\mathbb{R}^{n}$, where $D\in\mathbb{R}^{n\times n}$ is the shortest path distance matrix of $G$. These graphs were first studied by Steinerberger in the context of a notion of discrete curvature (``Curvature on graphs via equilibrium measures,’’ \emph{Journal of Graph Theory}, 103(3), 2023). This work has led to several open questions about distance exceptional graphs, including: What is the structure of such graphs? How can they be characterized? How rare are they? In this paper, we investigate these questions through the lens of a graph invariant we term the \emph{curvature index}. We show that a graph is distance exceptional if and only if this invariant vanishes, and we develop a calculus for this invariant under graph operations including the Cartesian product and graph join. As a result, we recover and generalize a number of known results in this area. We show that any graph $G$ can be realized as an induced subgraph of a distance exceptional graph $G’$. Moreover, in many cases, this embedding is an isometry. In turn, this leads to a number of methods for constructing distance exceptional graphs.
