Dominating induced matchings in graphs without a skew star

Korpelainen, Nicholas; Lozin, Vadim V. and Purcell, Christopher (2014). Dominating induced matchings in graphs without a skew star. Journal of Discrete Algorithms, 26 pp. 45–55.



We study the problem of determining whether a graph G has an induced matching that dominates every edge of the graph, which is also known as efficient edge domination. This problem is known to be NP-complete in general graphs, but it can be solved in polynomial time for graphs in some special classes, such as weakly chordal, P7-free or claw-free graphs. In the present paper we extend the polynomial-time solvability of the problem from claw-free graphs to graphs without a skew star, where a skew star is a tree with exactly three vertices of degree 1 being of distance 1,2,3 from the only vertex of degree 3.

Viewing alternatives


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions
No digital document available to download for this item

Item Actions