کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903100 1632401 2018 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Null decomposition of trees
ترجمه فارسی عنوان
تجزیه کامل درختان
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 836-850
نویسندگان
, ,