论文部分内容阅读
图的导出匹配可扩性和偶匹配可扩性是图论的新兴研究课题,旨在探讨图的导出匹配和偶匹配与完美匹配之间的结构性质。
称图G的匹配M是导出匹配,如果M及其关联的顶点构成一个导出子图,即G[M]=G[V(M)].称图G是导出匹配可扩的,如果G的每一个导出匹配都可以扩为G的完美匹配.称图G的匹配M是偶匹配,如果M关联的顶点导出的子图是一个二部图.称图G是偶匹配可扩的,如果G的每一个偶匹配都可以扩为G的完美匹配。
本文研究导出匹配可扩图和偶匹配可扩图的结构性质,并得到如下主要结果:
(1)证明了在一定条件下剖分边,膨胀点保持图的导出匹配可扩性。
(2)证明了紧割分解保持图的偶匹配可扩性。
(3)研究了图的导出匹配可扩性关于韧度的充分条件和必要条件。
(4)研究了一些特殊的图类的导出匹配与偶匹配可扩性,如:完全多部图、T2等.
(5)刻画了极大的导出匹配不可扩二部图。