Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9512604 | Discrete Mathematics | 2005 | 7 Pages |
Abstract
Kobler and Rotics gave a polytime algorithm for deciding if a graph has maximum induced matching and maximum matching the same size, and for finding a maximum induced matching in a graph where equality holds. We give a simple characterization of these graphs. Our characterization provides a simpler recognition algorithm.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Kathie Cameron, Tracy Walker,