Dominating induced matchings in graphs containing no long claw

Hertz, Alain; Lozin, Vadim; Ries, Bernard; Zamaraev, Viktor; de Werra, Dominique

doi:10.1002/jgt.22182

Back

Journal article

Dominating induced matchings in graphs containing no long claw

Hertz, Alain Department of Mathematics and Industrial Engineering
Lozin, Vadim Mathematics Institute
Ries, Bernard Department of Informatics
Zamaraev, Viktor Mathematics Institute
de Werra, Dominique Institute of Mathematics

2017

Published in:

Journal of Graph Theory. - 2017, vol. 88, no. 1, p. 18-39

graphs containing no long claw

English 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.

Faculty

Faculté des sciences économiques et sociales et du management

Department

Département d'informatique

Language