11-35
Graphs with Maximal Induced Matchings of the Same Size
by Baptiste, Ph.; Kovalyov, M.Y.; Orlovich, Y.L.; Werner, F.; Zverovich, I.E.
Preprint series: 11-35, Preprints
- MSC:
- 68Q15 Complexity classes, See also {03D15}
- 05C70 Factorization, matching, covering and packing
- 05C75 Structural characterization of types of graphs
Abstract: A graph is well-indumatched if all its maximal (with respect to set inclusion) 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 $(2P_5, K_{1, 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.
Keywords: Induced matching; Well-covered graph; Computational complexity; Forbidden induced subgraph.
The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.