三类不含拉普拉斯特征值1的树

摘要

设A（G）为图G的邻接矩阵，D（G）为图G的度对角矩阵，称L（G）=D（G）-A（G）为图G的拉普拉斯矩阵，则特征多项式?_G（μ）=det(μI-L（G）)的所有根称为图G的拉普拉斯特征值。一个端点的度不小于3,另一个端点的度等于1的路，被称为外部路。对于任意图G,如果G的外部路上包含P₃子图，则删除P₃不影响图G中拉普拉斯特征值1的重数。通过递归删除外部路上的P₃,刻画了不含拉普拉斯特征值1的星型树、双星树和三星树。

关键词

树 / 拉普拉斯矩阵 / 特征值 / 重数 / 零度