Options
The 2-Steiner distance matrix of a tree
Journal
Linear Algebra and Its Applications
ISSN
00243795
Date Issued
2022-12-15
Author(s)
Azimi, Ali
Sivasubramanian, Sivaramakrishnan
Abstract
Let T be a tree with vertex set V(T)={1,2,…,n}. The Steiner distance of a subset S⊆V(T) of vertices of T is defined to be the number of edges in a smallest connected subtree of T that contains all the vertices of S. The k-Steiner distance matrix Dk(T) of T is the (nk)×(nk) matrix whose rows and columns are indexed by subsets of vertices of size k. The entry in the row indexed by P and column indexed by Q is equal to Steiner distance of P∪Q. We consider the case when k=2 and show that rank(D2(T))=2n−p−1 where p is the number of pendant vertices (or leaves) in T. We construct a basis B for the row space of D2(T) and obtain a formula for the inverse of the nonsingular square submatrix D=D2(T)[B,B]. We also compute the determinant of D and show that its absolute value is independent of the structure of T and apply it to obtain the inertia of D2(T). Lastly, we determine the spectrum of 2-Steiner distance matrix of the star tree.
Subjects