Article ID Journal Published Year Pages File Type
431299 Journal of Discrete Algorithms 2014 11 Pages PDF
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, P7P7-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,31,2,3 from the only vertex of degree 3.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,