{
  "id": "1903.11566",
  "version": "v1",
  "published": "2019-03-27T17:29:18.000Z",
  "updated": "2019-03-27T17:29:18.000Z",
  "title": "Distance matrices of a tree: two more invariants, and in a unified framework",
  "authors": [
    "Projesh Nath Choudhury",
    "Apoorva Khare"
  ],
  "comment": "41 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "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_T)$, cof$(D_T)$, $D_T^{-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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-03-27T17:29:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C05",
      "05C20",
      "05C22",
      "05C25",
      "05C50",
      "05C83",
      "15A15"
    ],
    "keywords": [
      "distance matrix",
      "unified framework",
      "delete arbitrary pendant nodes",
      "multiplicative graham-hoffman-hosoya type formulas",
      "graham-hoffman-hosoya type result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 41,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}