A simple proof of Graham and Pollak's theorem

DOI10.1016/J.JCTA.2005.07.005MaRDI QIDQ2497973zbMATH OpenOpenAlexFDO

Authors Weigen Yan, Yeong-Nan Yeh

Publication date 4 August 2006

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcta.2005.07.005

zbMATH Keywords

determinantdistance matrixDodgson's determinant-evaluation rule

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15)

Review text

Let \(T\) be a tree with \(n\) vertices and \(D\) the \(n\times n\) distance matrix of \(T\). \textit{R. L. Graham} and \textit{H. O. Pollack} [Bell Syst. Tech. J. 50, 2495--2519 (1971; Zbl 0228.94020)] proved the following formula: \(\det(D)=-(n-1)(-2)^{n-2}\), which is independent of the structure of \(T\). Other proofs were given by R. L. Graham with co-authors. In this paper the authors give a further proof by induction over \(n\), using the Dodgson determinant evaluation rule \(\det(A) \det(A_2)= \det(A_{11})\det(A_{nn})-\det(A_{1n})\det(A_{n1})\), where \(A\) is an \(n\times n\) matrix with \(n>2\), \(A_{ij}\) is the minor of \(A\) obtained by deleting the \(i\)th row and \(j\)th column, and \(A_2\) is the minor of \(A\) obtained by deleting rows 1 and \(n\) and columns 1 and \(n\).

Recommendations

• Another simple proof of Graham and Pollak's theorem
• Determinant of the distance matrix of a tree with matrix weights
• Inverses of \(q\)-distance matrices of a tree
• Product distance matrix of a tree with matrix weights
• A \(q\)-analogue of Graham, Hoffman and Hosoya's theorem

Cites work

• Distance matrix polynomials of trees
• Dodgon's determinant-evaluation rule proved by TWO-TIMING MEN and WOMEN
• On the Addressing Problem for Loop Switching
• On the distance matrix of a directed graph
• On the distance matrix of a tree

Cited in

(23)

• Graph families with constant distance determinant
• Distance matrices of subsets of the Hamming cube
• On a conjecture of Graham and Lovász about distance matrices
• New proofs of Bapat and Sivasubramanian's theorems
• The determinants of \(q\)-distance matrices of trees and two quantities relating to permutations
• The product distance matrix of a tree with matrix weights on its arcs
• The distance matrix of a tree with weights on its arcs
• Proof of a conjecture of Graham and Lovász concerning unimodality of coefficients of the distance characteristic polynomial of a tree
• The inverse of the distance matrix of a distance well-defined graph
• Identities for minors of the Laplacian, resistance and distance matrices of graphs with arbitrary weights
• Decomposition of random graphs into complete bipartite graphs
• Distance matrices of a tree: two more invariants, and in a unified framework
• A q-analogue of distance matrix of block graphs
• A generalization of the Graham-Pollak tree theorem to Steiner distance
• A generalization of the Graham-Pollak tree theorem to even-order Steiner distance
• The Smith normal form of distance matrices of high dimensional trees
• On the decomposition of random hypergraphs
• The Laplacian and distance matrix of a signed tree
• Distance critical graphs
• Inverses of \(q\)-distance matrices of a tree
• Another simple proof of Graham and Pollak's theorem
• A new proof of a theorem of Graham and Pollak
• \(q\)-analogs of distance matrices of 3-hypertrees

This page was built for publication: A simple proof of Graham and Pollak's theorem

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