Distance Exceptional Graphs and the Curvature Index

A graph $G=(V,E)$ on n vertices is said to be distance exceptional if the equation Dx⃗ = 1⃗ admits no solution x⃗ⁿ, where Dn× 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,'' 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 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.