Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time
Let G = (V, E) be a finite undirected graph. An edge subset E′ ⊆ E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E′. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G. The DIM problem is -complete even fo...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
University of Zielona Góra
2022-11-01
|
Series: | Discussiones Mathematicae Graph Theory |
Subjects: | |
Online Access: | https://doi.org/10.7151/dmgt.2336 |
Summary: | Let G = (V, E) be a finite undirected graph. An edge subset E′ ⊆ E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E′. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G. The DIM problem is -complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for P7-free graphs and in polynomial time for P8-free graphs. In this paper, we solve it in polynomial time for P9-free graphs. |
---|---|
ISSN: | 2083-5892 |