2017/06/27 by Andreas Brandstädt, Brandstädt, Andreas, Raffaele Mosca +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1706.09301
openalex publication_date 2017/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V,E) be a finite undirected graph without loops and multiple edges. A subset M ⊆ E of edges is a \em dominating induced matching (\em d.i.m.) in G if every edge in E is intersected by exactly one edge of M. In particular, this means that M is an induced matching, and every edge not in M shares exactly one vertex with an edge in M. Clearly, not every graph has a d.i.m. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G; this problem is also known as the Efficient Edge Domination problem; it is the \em Efficient Domination problem for line graphs. The DIM problem is \NP-complete in general, and even for very restricted graph classes such as planar bipartite graphs with maximum degree 3. However, DIM is solvable in polynomial time for claw-free (i.e., S1,1,1-free) graphs, for S1,2,3-free graphs as well as for S2,2,2-free graphs, in linear time for P7-free graphs, and in polynomial time for P8-free graphs (Pk is a special case of Si,j,ℓ). In a paper by Hertz, Lozin, Ries, Zamaraev and de Werra, it was conjectured that DIM is solvable in polynomial time for Si,j,k-free graphs for every fixed i,j,k. In this paper, combining two distinct approaches, we solve it in polynomial time for S1,2,4-free graphs which generalizes the S1,2,3-free as well as the P7-free case.