Result: On Universal Threshold Graphs: On universal threshold graphs

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. Letndenote the set of threshold graphs withnvertices. A graph is calledn-universal if it contains every threshold graph withnvertices as an induced subgraph.n-universalthresholdgraphs are of special interest, since they are precisely thosen-universal graphs that do not contain any non-threshold induced subgraph.In this paper we shall studyminimumn-universal (threshold) graphs,i.e.n-universal (threshold) graphs having the minimum number of vertices.It is shown that for anyn≥ 3 there exist minimumn-universal graphs, which are themselves threshold, and others which are not.Two extremal minimumn-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 minimumn-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 minimumn-universal threshold graphT, an induced subgraphG' ofTisomorphic toG.