The additive-multiplicative distance matrix of a graph, and a novel third invariant

Abstract

Graham showed with Pollak and Hoffman-Hosoya that for any directed graph G with strong blocks Ge, the determinant det(DG) and cofactor-sum cof(DG) of the distance matrix DG can be computed from the same quantities for the blocks Ge. This was extended to trees - and in our recent work to any graph - with multiplicative and q-distance matrices. For trees, we went further and unified all previous variants with weights in a unital commutative ring, into a distance matrix with additive and multiplicative edge-data. n this work: (1) We introduce the additive-multiplicative distance matrix DG of every strongly connected graph G, using what we term the additive-multiplicative block-datum G. This subsumes the previously studied additive, multiplicative, and q-distances for all graphs. (2) We introduce an invariant ?(DG) that seems novel to date, and use it to show "master" Graham-Hoffman-Hosoya (GHH) identities, which express det(DG),cof(DG) in terms of the blocks Ge. We show how these imply all previous variants. (3) We show det(.),cof(.),k(.) depend only on the block-data for not just DG, but also several minors of DG. This was not studied in any setting to date; we show it in the "most general" additive-multiplicative setting, hence in all known settings. (4) We compute D1G in closed-form; this specializes to all known variants. In particular, we recover our previous formula for D1T for additive-multiplicative trees (which itself specializes to a result of Graham-Lovasz and answers a 2006 question of Bapat-Lal-Pati.) (5) We also show that not the Laplacian, but a closely related matrix is the "correct" one to use in D1G - for the most general additive-multiplicative matrix DG of each G. As examples, we compute in closed form det(DG),cof(DG),k(DG),D1G for hypertrees.