The 2-Steiner distance matrix of a tree.

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 D k (T) of T is the ( n k ) × ( n k ) 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 (D 2 (T)) = 2 n − p − 1 where p is the number of pendant vertices (or leaves) in T. We construct a basis B for the row space of D 2 (T) and obtain a formula for the inverse of the nonsingular square submatrix D = D 2 (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 D 2 (T). Lastly, we determine the spectrum of 2-Steiner distance matrix of the star tree. [ABSTRACT FROM AUTHOR]