A class of threshold and domishold graphs: equistable and equidominating graphs

AbstractA threshold graph (respectively domishold graph) is a graph for which the independent sets (respectively the dominating sets) can be characterized by the 0, 1-solutions of a linear Inequality (see [1] and [3]).We define here the graphs for which the maximal independent sets (respectively the minimal dominating sets) are characterized by the 0, 1-solutions of a linear equation. Such graphs are said to be equistable (respectively equldominating).We characterize (by their architectural structure and by forbidden induced subgraphs) threshold graphs and domishold graphs which are equistable or equidominating.A larger class of equistable graphs is also presented