Article ID Journal Published Year Pages File Type
9512604 Discrete Mathematics 2005 7 Pages PDF
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.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
The graphs with maximum induced matching and maximum matching the same size
Authors
, ,