Distance matrices of a tree: two more invariants, and in a unified framework

Abstract

In this paper, we introduce a more general framework for bi-directed weighted trees that has not been studied to date; our work is significant for three reasons. First, our setting strictly generalizes - and unifies - all variants of distance matrix studied to date (with coefficients in an arbitrary unital commutative ring) - including in Graham and Pollak (1971) above, as well as Graham and Lovasz (1978), Yan and Yeh (2006), Yan and Yeh (2007), Sivasubramanian (2010), and others. Second, our results strictly improve on state-of-the-art for every variant of the distance matrix studied to date, even in the classical Graham-Pollak case. Here are three results for trees: (1) We compute the minors obtained by deleting arbitrary equinumerous sets of pendant nodes (in fact, more general sub-forests) from the rows and columns of distance matrix, and show these minors depend only on the edge-data and not the tree-structure. (2) We compute a second function of the distance matrix: the sum of all its cofactors, termed distance matrix. We do so in our general setting and in stronger form, after deleting equinumerous pendant nodes (and more generally) as above - and show these quantities also depend only on the edge-data. (3) We compute in closed form the inverse of distance matrix extending a result of Graham and Lovasz (1978) and answering an open question of Bapat et al. (2006) in greater generality. Third, a new technique is to crucially use commutative algebra arguments - specifically, Zariski density - which to our knowledge are hitherto unused for such matrices/invariants, but are richly rewarding. We also explain why our setting is "most general", in that for more general edgeweights depend on the tree structure. In a sense, this completes the study of the invariants for distance matrices of trees with edge-data in a commutative ring. Our proofs use novel results for arbitrary bi-directed strongly connected graphs G: we prove a multiplicative analogue of an additive result by Graham et al. (1977), as well as a novel -version there of. In particular, we provide closed-form expressions for Dg, cof(Dg) and Dg-1 in terms of their strong blocks. We then show how this subsumes the classical 1977 result, and provide sample applications to adding pendant trees and to cycle-clique graphs (including cactus/polycyclic graphs and hypertrees), subsuming variants in the literature. The final section introduces and computes a third - and novel - invariant for trees, as well as a parallel Graham-Hoffman-Hosoya type result for our "most general" distance matrix Dt.