2025/10/06 by Carlos A. Alfaro, Alfaro, Carlos A., Jesús Uriel Medrano +3 · 1 citation
Mathematics · Computer Science · #Graph theory and applications #Advanced Topics in Algebra #Matrix Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2510.04471
Graham-Lovász-Pollak \citeGL,GP obtained the celebrated formula det(\sf D(Tn+1))=(-1)nn2n-1, for the determinant of the distance matrix \sf D(Tn+1) for any tree Tn+1 with n+1 vertices. Later, Hou and Woo \citeHW extended this formula to the Smith normal form (SNF) obtaining that \SNF(\sf D(Tn+1))=\sf I2⊕ 2\sf In-2⊕ [2n], for any tree Tn+1 with n+1 vertices. A k-\it tree is either a complete graph on k vertices or a graph obtained from a smaller k-tree by adjoining a new vertex together with k edges connecting it to a k-clique. If τ and τ' are d-cliques in a k-tree T, a d-\it walk between τ and τ' is a finite sequence τ1σ1τ2σ2⋯τl, where τ1=τ, τl=τ', and the d-cliques τi and τi+1 are incident to the same (d+1)-clique σi. For d∈\1,…,k\, the d-\it distance from the d-cliques τ and τ' is the number of (d+1)-cliques in a minimum d-walk from τ and τ', and is denoted by \distd(τ,τ'). Let cd denote the number of d-cliques in the k-tree T. Then the d-distance matrix \sf Dd(T) of the k-tree T is the cd× cd matrix, indexed by the d-cliques of T, such that the (i,j)-entry is 0 if i=j, and \distd(τi,τj) otherwise. Here, we show that, for k and n fixed, the SNF of the k-distance matrix is the same for any k-tree with n vertices. Specifically, for any k-tree Tn with n vertices such that n≥ k+2, the Smith normal form of \sf Dk(Tn) is \sf I(k-1)(n-k)+2⊕ (k+1)\sf In-k-2⊕ [k(k+1)(n-k)], which extends Graham-Lovász-Pollak and Hou-Woo results.