Graphs with Maximal Induced Matchings of the Same Size

What is it about?

This paper deals with so-called well-indumatched graphs (i.e., all its maximal induced matchings are of the same size). For some recognition problems complexity results are given. The class of perfectly well-indumatched graphs (i.e., every induced subgraph is well-indumatched) is characterized in terms of forbidden induced subgraphs. We also give some polynomial algorithms for some problems for perfectly well-indumatched graphs.

Featured Image