拟轮图的导出匹配可扩性

摘要：

从导出匹配可扩图的定义、结构出发,研究了拟轮图的性质, 构造了一类新的导出匹配可扩图Γn. 主要结果如下:(1)判定具有奇数个顶点的图几乎导出匹配可扩性是co-NP-完全的. (2)Γn中的任何一个图均是边数为5n-6的导出匹配可扩的拟轮图.

关键词：匹配、完美匹配、导出匹配可扩图

所属期刊栏目：38

分类号：O157.5(代数、数论、组合理论)

资助基金：河南省教育厅自然科学基金资助项目2004110008

在线出版日期：2008-11-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：458-460