Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9513462 | Discrete Mathematics | 2005 | 10 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniemi, Renu Laskar,