Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421398 | Discrete Applied Mathematics | 2008 | 16 Pages |
Abstract
A graph is called equistable when there is a non-negative weight function on its vertices such that a set S of vertices has total weight 1 if and only if S is maximal stable. We show that a necessary condition for a graph to be equistable is sufficient when the graph in question is distance-hereditary. This is used to design a polynomial-time recognition algorithm for equistable distance-hereditary graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ephraim Korach, Uri N. Peled, Udi Rotics,