Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431299 | Journal of Discrete Algorithms | 2014 | 11 Pages |
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
Nicholas Korpelainen, Vadim V. Lozin, Christopher Purcell,