Configuration-Induced Metrics and the Irreversibility of Graph Distance Averaging

Abstract: Finite metrics obtained by averaging shortest-path distances over multiple connected graphs arise naturally in combinatorics and metric geometry, yet their structural properties remain poorly understood. This work develops a complete theory of such configuration-induced metrics. We formalize metric equivalence, showing that distinct configuration families may induce identical metrics, and demonstrate that reconstruction of generating configurations from the metric is generically impossible once averaging is non-trivial. To isolate irreducible structure, we introduce metric redundancy and metric minimality, providing exact analytic characterizations and proving existence of minimal realizations. The central result presents intrinsic non-reconstructibility: for vertex sets of size at least six, infinitely many nonisomorphic metric-minimal configuration families induce the same metric without any distance-preserving correspondence. A sharp rigidity boundary is identified: a configurationinduced metric is rigid if and only if it arises from a single graph. All recoverable metric invariants are classified, yielding a mathematically and computationally consistent formulation. Keywords: Configuration-induced metrics; Metric equivalence; Non-reconstructibility; Graph distance averaging