A generalization of alpha-critical graphs in connection with linear ordering polytopes

A graph is alpha-critical is it has no isolated vertex and its stability number increases whenever an edge is removed. Alpha-critical graphs are well-studied and have nice structural properties. In this talk, we introduce a weighted generalization of these graphs. The starting point is a scheme associating to any vertex-weighted graph a corresponding valid inequality for the linear ordering polytope. Our aim is to understand the weighted graphs giving the strongest inequalities, i.e., those defining facets of the polytope. It turns out that when the weighting is everywhere one, these graphs are exactly the connected alpha-critical ones. We will present extensions of some results from the theory of alpha-critical graphs to our generalization, as well as new findings that are specific to the weighted case.