Edge Elimination and Weighted Graph Classes.

Edge-weighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from an edge-weighted graph by removing all sufficiently light edges. This naturally leads to a generalization of the concept of a graph class to the weighted case by requiring that all level graphs belong to the class. We examine some types of monotonicity of graph classes, such as sandwich monotonicity, to construct edge elimination schemes of edge-weighted graphs. This leads to linear-time recognition algorithms of weighted graphs for which all level graphs are split, threshold, or chain graphs.