首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 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.
Keywords:Trees  Eigenvectors  Null space  Independence number  Matching number  Maximum matchings  Independent sets
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号