Hertz, Alain Lozin, Vadim Ries, Bernard Zamaraev, Viktor de Werra, Dominique 2017 An induced matching 𝑀 in a graph 𝐺 is dominating if every edge not in 𝑀 shares exactly one vertex with an edge in 𝑀. The DOMINATING INDUCED MATCHING problem (also known as EFFICIENT EDGE DOMINATION) asks whether a graph 𝐺 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 algorithmto solve the DOMINATING 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. application/pdf https://folia.unifr.ch/global/documents/307795 https://folia.unifr.ch/documents/307795/files/jgt_rero.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1002/jgt.22182 info:eu-repo/semantics/openAccess License undefined Journal of Graph Theory. - 2017, vol. 88, no. 1, p. 18-39 dominating induced matching graphs containing no long claw polynomial-time algorithm info:eu-repo/classification/udc/33 Dominating induced matchings in graphs containing no long claw http://purl.org/coar/resource_type/c_6501