The ancestral matrix of a rooted tree

DOI10.1016/J.LAA.2019.04.004MaRDI QIDQ2419059zbMATH OpenOpenAlexWikidataFDO

Authors Eric Ould Dadah Andriantiana, Kenneth Dadedzi, Stephan Wagner

Publication date 29 May 2019

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.03364

zbMATH Keywords

ancestral matrixcharacteristic polynomialrooted treespectral radiusspectrum

Mathematics Subject Classification ID

Trees (05C05) Graph polynomials (05C31) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Given a rooted tree $T$ with leaves $v_1,v_2,ldots,v_n$, we define the ancestral matrix $C(T)$ of $T$ to be the $nimesn$ 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.

Review text

In this paper, the authors are interested in the combinatorial and spectral properties of a matrix associated with a rooted tree. Given a rooted tree \(T\) with leaves \(v_1, v_2, \dots, v_n\), they define the ancestral matrix \(C(T)\) of \(T\) to be the \(n\times 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\). They study properties of this matrix, in particular regarding its spectrum: they obtain several upper and lower bounds for the eigenvalues in terms of other tree parameters. They 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.

Recommendations

• The spectra of the adjacency matrix and Laplacian matrix for some balanced trees
• On the characteristic and Laplacian polynomials of trees
• On the spectra of some weighted rooted trees and applications
• On the spectra of certain rooted trees
• On the spectrum of finite, rooted homogeneous trees

Cites work

• A Course in Enumeration
• Binomial determinants, paths, and hook length formulae
• Distance matrix polynomials of trees
• Graphs with given degree sequence and maximal spectral radius
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 3222645 (Why is no real title available?)
• On meet matrices on posets
• On the Addressing Problem for Loop Switching
• On the distance matrix of a tree
• The Laplacian spectral radii of trees with degree sequences
• Wiener index versus maximum degree in trees

Cited in

(3)

• Generation matrix: an embeddable matrix representation for hierarchical trees
• The level matrix of a tree and its spectrum
• A Second-Moment Theory for Floating-Point Reduction Trees

This page was built for publication: The ancestral matrix of a rooted tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2419059)