Null decomposition of trees |
| |
Authors: | Daniel A Jaume Gonzalo Molina |
| |
Institution: | Departamento de Matemáticas, Facultad de Ciencias Físico-Matemáticas y Naturales, Universidad Nacional de San Luis, 1er. piso, Bloque II, Oficina 54, Ejército de los Andes 950, San Luis, D5700HHW, Argentina |
| |
Abstract: | Let be a tree. We show that the null space of the adjacency matrix of has relevant information about the structure of . 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. |
| |
Keywords: | Trees Eigenvectors Null space Independence number Matching number Maximum matchings Independent sets |
本文献已被 ScienceDirect 等数据库收录! |
|