首页 | 本学科首页   官方微博 | 高级检索  
     


Perfect stables in graphs
Authors:Cornelius Croitoru  Emilian Suditu
Affiliation:Department of Mathematics, University of IASI, IASI, R-6600 Romania
Abstract:A perfect stable in a graph G is a stable S with the property that any vertex of G is either in S or adjacent with at least two vertices which are in S. This concept is an obvious generalization of the notion of perfect matching. In this note, the problem of deciding if a given graph has a perfect stable is considered. This problem is shown to be in general NP-complete, but polynomial for K1,3-free graphs.
Keywords:Stable  perfect matching
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号