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

Matching and Laplacian Eigenvalues

作　　者：章舜哲 陆玫[2] 刘慧清 ZHANG Shunzhe;LU Mei;LIU Huiqing(Hubei Key Laboratory of Applied Mathematics,Faculty of Mathematics and Statistics,Hubei University,Wuhan 430062,China;Department of Mathematical Sciences,Tsinghua University,Beijing 100084,China)

机构地区：[1]湖北大学数学与统计学学院湖北省应用数学重点实验室,武汉430062 [2]清华大学数学科学系,北京100084

出　　处：《应用数学学报》2019年第2期162-166,共5页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(11771247;11571096)资助项目

摘　　要：设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是因子临界的.本文中,我们给出了判定一个图有完美匹配、或者几乎完美匹配或者是因子临界的拉普拉斯谱条件.Let G be a graph with n vertices.A perfect matching of G is a set M of edges such that no two edges are incident with a common vertex and each vertex of G is incident to some edge in M.A near-perfect matching of G is a matching M such that it is incident with all vertices of G except exactly one.If G-v has a perfect matching for every choice of v∈ V(G),then G is said to be factor-critical.In this paper,we present some sufficient conditions for existences of a perfect matching,a near-perfect matching or factor-critical of G in terms of the Laplacian eigenvalues.

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

分 类 号：O157.5[理学—数学]