Dominating induced matchings in graphs containing no long claw. Issue 1 (6th September 2017)

• Record Type: Journal Article
• Authors: Hertz, Alain; Lozin, Vadim; Ries, Bernard; Zamaraev, Viktor; de Werra, Dominique
• Is Part Of: Journal of graph theory. Volume 88:Issue 1(2018)
• Page Start: 18
• Page End: 39
• Publication Date: 2017-09-06
• Subjects: dominating induced matching -- graphs containing no long claw -- polynomial‐time algorithm; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22182
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: An induced matching M in a graph G is dominating if every edge not in M shares exactly one vertex with an edge in M . Thedominating induced matching problem (also known asefficient edge domination ) asks whether a graph G contains a dominating induced matching. This problem is generally NP‐complete, but polynomial‐time solvable for graphs with some special properties. In particular, it is solvable in polynomial time for claw‐free graphs. In the present article, we provide a polynomial‐time algorithm to solve thedominating induced matching problem for graphs containing no long claw, that is, no induced subgraph obtained from the claw by subdividing each of its edges exactly once.