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.

DOI: https://doi.org/10.1016/j.jda.2013.11.002

Abstract

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, P₇-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

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI