The ancestral matrix of a rooted tree

DOI10.1016/J.LAA.2019.04.004zbMATH Open1483.05091arXiv1809.03364OpenAlexW2889708013WikidataQ128086277 ScholiaQ128086277MaRDI QIDQ2419059FDOQ2419059

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)

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.

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

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

zbMATH Keywords

spectral radiusspectrumcharacteristic polynomialrooted treeancestral matrix

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Binomial determinants, paths, and hook length formulae
• On the Addressing Problem for Loop Switching
• On the distance matrix of a tree
• Distance matrix polynomials of trees
• Wiener index versus maximum degree in trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Laplacian spectral radii of trees with degree sequences
• On meet matrices on posets
• A Course in Enumeration
• Graphs with given degree sequence and maximal spectral radius
• Title not available (Why is that?)

Cited In (2)

• The level matrix of a tree and its spectrum
• Generation matrix: an embeddable matrix representation for hierarchical 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)