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 whether a graph is well-indumatched is a co-NP-complete problem even for (2P5,K1,5)-free graphs. We then show that decision problems Independent Dominating Set, Independent Set, and...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2017-01, Vol.216, p.15-28
Main Authors: Baptiste, Philippe, Kovalyov, Mikhail Y., Orlovich, Yury L., Werner, Frank, Zverovich, Igor E.
Format: Article
Language:English
Subjects:
Computational complexity
Forbidden induced subgraph
Graphs
Induced matching
Optimization problem
Polynomials
Studies
Well-covered graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A graph is well-indumatched if all its maximal induced matchings are of the same size. We first prove that recognizing whether a graph is well-indumatched is a co-NP-complete problem even for (2P5,K1,5)-free graphs. We then show that decision problems Independent Dominating Set, Independent Set, and Dominating Set are NP-complete for the class of well-indumatched graphs. We also show that this class is a co-indumatching hereditary class, i.e., it is closed under deleting the end-vertices of an induced matching along with their neighborhoods, and we characterize well-indumatched graphs in terms of forbidden co-indumatching subgraphs. We prove that recognizing a co-indumatching subgraph is an NP-complete problem. We introduce a perfectly well-indumatched graph, in which every induced subgraph is well-indumatched, and characterize the class of these graphs in terms of forbidden induced subgraphs. Finally, we show that the weighted versions of problems Independent Dominating Set and Independent Set can be solved in polynomial time for perfectly well-indumatched graphs, but problem Dominating Set is NP-complete.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2016.08.015