Perfeziona i miei risultati

Dominating induced matchings in graphs containing no long claw

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

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

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