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 等数据库收录! |
|