Article ID Journal Published Year Pages File Type
9513462 Discrete Mathematics 2005 10 Pages PDF
Abstract
For a graph property P, we define a P-matching as a set M of disjoint edges such that the subgraph induced by the vertices incident to M has property P. Previous examples include strong/induced matchings and uniquely restricted matchings. We explore the general properties of P-matchings, but especially the cases where P is the property of being acyclic or the property of being disconnected. We consider bounds on and the complexity of the maximum cardinality of a P-matching and the minimum cardinality of a maximal P-matching.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,