Premium
Equistable graphs
Author(s) -
Mahadev N. V. R.,
Peled Uri N.,
Sun Feng
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180307
Subject(s) - mathematics , combinatorics , cograph , pathwidth , 1 planar graph , chordal graph , indifference graph , discrete mathematics , outerplanar graph , graph , split graph , block graph , line graph
An equistable graph is a graph for which the incidence vectors of the maximal stable sets are the 0–1 solutions of a linear equation. A necessary condition and a sufficient condition for equistability are given. They are used to characterize the equistability of various classes of perfect graphs, outerplanar graphs, and pseudothreshold graphs. Some classes of equistable graphs are shown to be closed under graph substitution.