拟轮图的导出匹配可扩性  

Induced Matching Extendability of Quasi-Wheel Graphs

作　　者：闫运生[1] 林浩[1] 

机构地区：[1]河南工业大学理学院,河南郑州450052

出　　处：《河南大学学报（自然科学版）》2008年第5期458-460,共3页Journal of Henan University:Natural Science

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

摘　　要：从导出匹配可扩图的定义、结构出发,研究了拟轮图的性质,构造了一类新的导出匹配可扩图Γn.主要结果如下:(1)判定具有奇数个顶点的图几乎导出匹配可扩性是co-NP-完全的.(2)Γn中的任何一个图均是边数为5n-6的导出匹配可扩的拟轮图.This paper bagins with the properties and structure of induced matching extendable graphs. The properties of Quasi-Wheel Graphs are studied . A class of induced matching extendable graph is created. The main results of this paper are as follows： （1） The decision of the almost induced matching extendability of graphs with odd vertices is co-NP-complete. （2） Every graph in Гn is an induced matching extendable quasi-wheel graph with 5n - 6 edges.

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

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