Tree decomposition by eigenvectors

DOI10.1016/J.LAA.2008.07.015MaRDI QIDQ958004zbMATH OpenOpenAlexFDO

Authors T. Sander, J. W. Sander

Publication date 2 December 2008

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

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

zbMATH Keywords

basiscomposition-decomposition techniqueeigenspace basematching propertiesnull spaceskeleton foresttree eigenvectors

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: In this work a composition-decomposition technique is presented that correlates tree eigenvectors with certain eigenvectors of an associated so-called skeleton forest. In particular, the matching properties of a skeleton determine the multiplicity of the corresponding tree eigenvalue. As an application a characterization of trees that admit eigenspace bases with entries only from the set {0, 1,-1} is presented. Moreover, a result due to Nylen concerned with partitioning eigenvectors of tree pattern matrices is generalized.

Recommendations

• Changes in vertex status and the fundamental decomposition of a tree relative to a multiple (parter) eigenvalue
• Null decomposition of trees
• Constructing trees with given eigenvalues and angles
• scientific article; zbMATH DE number 977801
• On the core-nilpotent decomposition of trees

Cites work

• \(\{-1,0,1\}\)-basis for the null space of a forest
• Eigenspaces of graphs
• Eigenvectors of acyclic matrices
• Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of a matrix
• Graph partitioning by eigenvectors
• scientific article; zbMATH DE number 1248194 (Why is no real title available?)
• scientific article; zbMATH DE number 977801 (Why is no real title available?)
• scientific article; zbMATH DE number 1491632 (Why is no real title available?)
• scientific article; zbMATH DE number 798644 (Why is no real title available?)
• scientific article; zbMATH DE number 3414355 (Why is no real title available?)
• Null space structure of tree-patterned matrices
• On simply structured bases of tree kernels
• On the construction of graphs of nullity one
• On the minimum number of distinct eigenvalues for a symmetric matrix whose graph is a given tree
• Partly zero eigenvectors and matrices that satisfyAu=b
• Reducing the adjacency matrix of a tree
• Trees with maximum nullity

Cited in

(6)

• Null decomposition of trees
• On the core-nilpotent decomposition of trees
• Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
• The non-negative spectrum of a digraph
• Nullspace vertex partition in graphs
• Tree decomposition

This page was built for publication: Tree decomposition by eigenvectors

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