Dominating induced matchings in S₁ , 2 , 4-free graphs

DOI10.1016/J.DAM.2018.09.028MaRDI QIDQ2174557zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Raffaele Mosca

Publication date 21 April 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.09301

zbMATH Keywords

\( S_{1, 2, 4}\)-free graphsdominating induced matchingefficient edge dominationpolynomial time algorithm

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Let $G=(V,E)$ be a finite undirected graph without loops and multiple edges. A subset $MsubseteqE$ 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 emph{Dominating Induced Matching} (emph{DIM}) problem asks for the existence of a d.i.m. in $G$; this problem is also known as the emph{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., $S_{1,1,1}$-free) graphs, for $S_{1,2,3}$-free graphs as well as for $S_{2,2,2}$-free graphs, in linear time for $P_7$-free graphs, and in polynomial time for $P_8$-free graphs ($P_k$ is a special case of $S_{i,j,ell}$). In a paper by Hertz, Lozin, Ries, Zamaraev and de Werra, it was conjectured that DIM is solvable in polynomial time for $S_{i,j,k}$-free graphs for every fixed $i,j,k$. In this paper, combining two distinct approaches, we solve it in polynomial time for $S_{1,2,4}$-free graphs which generalizes the $S_{1,2,3}$-free as well as the $P_7$-free case.

Recommendations

• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
• Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time
• Dominating induced matchings for \(P _{7}\)-free graphs in linear time
• Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
• Dominating induced matchings for \(P_7\)-free graphs in linear time

Cites work

• Dominating induced matchings for \(P_7\)-free graphs in linear time
• Dominating induced matchings in graphs containing no long claw
• Dominating induced matchings in graphs without a skew star
• Efficient edge domination on hole-free graphs in polynomial time
• Efficient edge domination problems in graphs
• Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Perfect codes in graphs
• Perfect edge domination and efficient edge domination in graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs

Cited in

(6)

• Finding dominating induced matchings in P₉-free graphs in polynomial time
• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
• Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time
• Graphs whose vertices of degree at least 2 lie in a triangle
• Perfect edge domination in P₆-free graphs and in graphs without efficient edge dominating sets
• Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time

This page was built for publication: Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174557)