Graphs with Maximal Induced Matchings of the Same Size

A graph is well-indumatched if all its maximal induced matchings are of the same size. We first prove that recognizing the class WIM of well-indumatched graphs is a co-NP-complete problem even for (2P5, K1,5)-free graphs. We then show that the well-known decision problems such as Independent Dominating Set, Independent Set, and Dominating Set are NP-complete for well-indumatched graphs. We also show that WIM is a co-indumatching hereditary class and characterize well-indumatched graphs in terms of forbidden co-indumatching subgraphs. However, we prove that recognizing co-indumatching subgraphs is an NP-complete problem. A graph G is perfectly well-indumatched if every induced subgraph of G is well-indumatched. We characterize the class of perfectly well-indumatched graphs in terms of forbidden induced subgraphs. Finally, we show that both Independent Dominating Set and Independent Set can be solved in polynomial time for perfectly well-indumatched graphs, even in their weighted versions, but Dominating Set is still NP-complete.