Isometric embedding and spectral constraints for weighted graph metrics

Abstract

A weighted graph $\varphi G$ encodes a finite metric space $D_{\varphi G}$. When is $D$ totally decomposable? When does it embed in ${\ell }_1$ space? When does its representing matrix have $\le 1$ positive eigenvalue? We give useful lemmata and prove that these questions can be answered without examining $\varphi$ if and only if $G$ has no $K_{2,3}$ minor. We also prove results toward the following conjecture. $D_{\varphi G}$ has $\le n$ positive eigenvalues for all $\varphi$, if and only if $G$ has no $K_{2,3,...,3}$ minor, with $n$ threes.