Zurück zu den Preprints des Jahres 2011


2011-35

Graphs with Maximal Induced Matchings of the Same Size

by Baptiste, Ph.; Kovalyov, M.Y.; Orlovich, Y.L.; Werner, F.; Zverovich, I.E..


Series: 2011-35, Preprints

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
05C70 Factorization, matching, partitioning, covering and packing
05C75 Structural characterization of families 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.