Article ID Journal Published Year Pages File Type
421398 Discrete Applied Mathematics 2008 16 Pages PDF
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.

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