Homogeneous linear recurrence relations of the determinants of distance matrices of trees

Abstract

In 1971, by induction on $n$ and using a two-term linear recurrence relation, Graham and Pollak got a beautiful formula $$\det (D_n)=-(n-1)(-2{)}^{n-2}$$ on the determinant of distance matrix $D_n$ of a tree $T_n$ on $n$ vertices. The recurrence relations are very crucial when proving this formula by inductive method: in 2006, Yan and Yeh used two-term and three-term recurrence relations; in 2020, Du and Yeh used a homogeneous linear three-term recurrence relation. In this paper, we analyze the subtree structure of the tree and find four-term, five-term, six-term and seven-term homogeneous linear recurrence relations on $\det (D_n)$, as a corollary new proofs of Graham and Pollak's formula can be given.