Chapter 10
Threshold graphs
Martin Charles Golumbic
Publisher Summary
This chapter discusses a particularly simple technique for distinguishing between stable and nonstable subsets of vertices in a special class of graphs. The graphs that admit this technique, which involves assigning certain weights to the vertices, are called threshold graphs. The chapter introduces the notion of threshold dimension. An induced subgraph of a threshold graph is a threshold graph. Therefore, any graph that contains an induced subgraph isomorphic to one of those is not threshold. The threshold dimension θ (G) of an arbitrary graph G can be defined in an alternate but equivalent manner using threshold graphs. Take θ (G) to be the minimum number of threshold graphs ...
