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

DOI10.1016/J.EJC.2023.103787arXiv1903.11566MaRDI QIDQ6081116FDOQ6081116

Authors: Projesh Nath Choudhury, Apoorva Khare 

Publication date: 25 October 2023

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Graham-Pollak showed that for $D=D_T$ the distance matrix of a tree $T$, det$(D)$ depends only on its number of edges. Several other variants of $D$, including directed/multiplicative/$q$- versions were studied, and always, det$(D)$ depends only on the edge-data. We introduce a general framework for bi-directed weighted trees, with threefold significance. First, we improve on state-of-the-art for all known variants, even in the classical Graham-Pollak case: we delete arbitrary pendant nodes (and more general subsets) from the rows/columns of $D$, and show these minors do not depend on the tree-structure. Second, our setting unifies all known variants (with entries in a commutative ring). We further compute in closed form the inverse of $D$, extending a result of Graham-Lovasz [Adv. Math. 1978] and answering a question of Bapat-Lal-Pati [Lin. Alg. Appl. 2006]. Third, we compute a second function of the matrix $D$: the sum of all its cofactors, cof$(D)$. This was worked out in the simplest setting by Graham-Hoffman-Hosoya (1978), but is relatively unexplored for other variants. We prove a stronger result, in our general setting, by computing cof$(.)$ for minors as above, and showing these too depend only on the edge-data. Finally, we show our setting is the 'most general possible', in that with more freedom in the edgeweights, det$(D)$ and cof$(D)$ depend on the tree structure. In a sense, this completes the study of the invariant det$(D_T)$ (and cof$(D_T)$) for trees $T$ with edge-data in a commutative ring. Moreover: for a bi-directed graph $G$ we prove multiplicative Graham-Hoffman-Hosoya type formulas for det$(D_G)$, cof$(D_G)$, $D_G^{-1}$. We then show how this subsumes their 1978 result. The final section introduces and computes a third, novel invariant for trees and a Graham-Hoffman-Hosoya type result for our "most general" distance matrix $D_T$.

Full work available at URL: https://arxiv.org/abs/1903.11566

Recommendations

• Determinant of the distance matrix of a tree with matrix weights
• Inverses of \(q\)-distance matrices of a tree
• A simple proof of Graham and Pollak's theorem
• Product distance matrix of a tree with matrix weights
• Product distance matrix of a graph and squared distance matrix of a tree

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Cites Work

• On the Addressing Problem for Loop Switching
• Distance matrix polynomials of trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• A \(q\)-analogue of the distance matrix of a tree
• A simple proof of Graham and Pollak's theorem
• Product distance matrix of a tree with matrix weights
• The product distance matrix of a tree with matrix weights on its arcs
• The distance matrix of a tree with weights on its arcs
• The distance matrix of a bidirected tree
• Product distance matrix of a graph and squared distance matrix of a tree
• The mutually beneficial relationship of graphs and matrices
• Combinatorial Nullstellensatz
• On the distance matrix of a directed graph
• On distance matrices and Laplacians
• Inverses of triangular matrices and bipartite graphs
• A combinatorial approach to matrix theory and its applications
• Inverse of the distance matrix of a cactoid digraph
• Inverse of the distance matrix of a cycle-clique graph
• \(q\)-analogs of distance matrices of 3-hypertrees
• The determinants of \(q\)-distance matrices of trees and two quantities relating to permutations
• Inverses of \(q\)-distance matrices of a tree
• On the determinant of \(q\)-distance matrix of a graph
• A \(q\)-analogue of Graham, Hoffman and Hosoya's theorem

Cited In (1)

• The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra

This page was built for publication: Distance matrices of a tree: two more invariants, and in a unified framework

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081116)