On Universal Threshold Graphs
P. L. Hammer, Alexander K. Kelmans · Combinatorics Probability Computing · 1994
A graphGisthresholdif there exists a ‘weight’ functionw:V(G) →Rsuch that the total weight of any stable set ofGis less than the total weight of any non-stable set ofG. Let ndenote the set of threshold graphs withnvertices. A graph is called n-universal if it contains every threshold graph withnvertices as an induced subgraph. n-universalthresholdgraphs are of special interest, since they are precisely those n-universal graphs that do not contain any non-threshold induced subgraph. In this paper we shall studyminimum n-universal (threshold) graphs,i.e. n-universal (threshold) graphs having the minimum number of vertices. It is shown that for anyn≥ 3 there exist minimum n-universal graphs, which are themselves threshold, and others which are not. Two extremal minimum n-universal graphs having respectively the minimum and the maximum number of edges are described, it is proved that they are unique, and that they are threshold graphs. The set of all minimum n-universal threshold graphs is then described constructively; it is shown that it forms a lattice isomorphic to then− 1 dimensional Boolean cube, and that the minimum and the maximum elements of this lattice are the two extremal graphs introduced above. The proofs provide a (polynomial) recursive procedure that determines for any threshold graphGwithnvertices and for any minimum n-universal threshold graphT, an induced subgraphG' ofTisomorphic toG.