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

来源：应用数学学报杂志2019年第2期北京时间：

作者：章舜哲, 陆玫, 刘慧清

单位：1. 湖北大学数学与统计学学院, 湖北省应用数学重点实验室, 武汉 430062;<br>2. 清华大学数学科学系, 北京 100084;<br>3. 湖北大学数学与统计学学院, 湖北省应用数学重点实验室, 武汉 430062

摘要：设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是因子临界的.本文中，我们给出了判定一个图有完美匹配、或者几乎完美匹配或者是因子临界的拉普拉斯谱条件.

关键词：拉普拉斯特征值,完美匹配,几乎完美匹配,因子临界