Null decomposition of trees

JAUME, DANIEL A.; MOLINA, GONZALO

DISCRETE MATHEMATICS

ELSEVIER SCIENCE BV

Año: 2018 vol. 341 p. 836 - 850

0012-365X

Let T be a tree. We show that the null space of the adjacency matrix of T has relevant information about the structure of T. We introduce the Null Decomposition of trees, which is a decomposition into two different types of trees: N-trees and S-trees. N-trees are the trees that have a unique maximum (perfect) matching. S-trees are the trees with a unique maximum independent set. We obtain formulas for the independence number and the matching number of a tree using this decomposition. We also show how the number of maximum matchings and the number of maximum independent sets in a tree are related to its null decomposition.