图的匹配与拉普拉斯特征值

摘要：设G=(V(G),E(G))是一个图,M是E(G)的一个子集。如果M中任意两条边均无公共端点,则称M为图G的匹配。如果图G的一个匹配M中的边恰好关联G的每一个顶点,则称M为图G的完美匹配。如果图G中除了一个顶点以外,其他所有顶点都与匹配M中的边相关联,则称M为图G的几乎完美匹配。如果对任意v∈V(G),G-v均有完美匹配,则称G是因子临界的。本文中,我们给出了判定一个图有完美匹配、或者几乎完美匹配或者是因子临界的拉普拉斯谱条件。