Monday, August 31, 2015

Threshold graphs and interval orders

Threshold graphs like interval orders have the property that each element is determined by some vertex invariant in all substructures. In threshold graphs all elements are determined by degree. In interval orders all elements are determined entirely by their interval representations. Both of these properties are maintained in forbidden substructures of each of these structures. Weak orders are the special class of interval orders whose elements are determined in terms of degrees. Threshold orders are interval orders with threshold comparability.