TY - JOUR
T1 - The ancestral matrix of a rooted tree
AU - Andriantiana, Eric O.D.
AU - Dadedzi, Kenneth
AU - Wagner, Stephan
N1 - Publisher Copyright:
© 2019 Elsevier Inc.
PY - 2019/8/15
Y1 - 2019/8/15
N2 - Given a rooted tree T with leaves v 1 ,v 2 ,…,v n , we define the ancestral matrix C(T) of T to be the n×n matrix for which the entry in the i-th row, j-th column is the level (distance from the root) of the first common ancestor of v i and v j . We study properties of this matrix, in particular regarding its spectrum: we obtain several upper and lower bounds for the eigenvalues in terms of other tree parameters. We also find a combinatorial interpretation for the coefficients of the characteristic polynomial of C(T), and show that for d-ary trees, a specific value of the characteristic polynomial is independent of the precise shape of the tree.
AB - Given a rooted tree T with leaves v 1 ,v 2 ,…,v n , we define the ancestral matrix C(T) of T to be the n×n matrix for which the entry in the i-th row, j-th column is the level (distance from the root) of the first common ancestor of v i and v j . We study properties of this matrix, in particular regarding its spectrum: we obtain several upper and lower bounds for the eigenvalues in terms of other tree parameters. We also find a combinatorial interpretation for the coefficients of the characteristic polynomial of C(T), and show that for d-ary trees, a specific value of the characteristic polynomial is independent of the precise shape of the tree.
KW - Ancestral matrix
KW - Characteristic polynomial
KW - Rooted tree
KW - Spectral radius
KW - Spectrum
UR - http://www.scopus.com/inward/record.url?scp=85064266962&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2019.04.004
DO - 10.1016/j.laa.2019.04.004
M3 - Article
AN - SCOPUS:85064266962
SN - 0024-3795
VL - 575
SP - 35
EP - 65
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
ER -