On rank-monotone graph operations and minimal obstruction graphs for the Lovász–Schrijver SDP hierarchy

We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász–Schrijver SDP operator \({{\,\textrm{LS}\,}}_+\) ${\text{LS}}_{+}$ , with a particular focus on finding and characterizing the smallest graphs with a given \({{\,\textrm{LS}\,}}_+\) ${\text{LS}}_{+}$ -rank (the needed number of iterations of the \({{\,\textrm{LS}\,}}_+\) ${\text{LS}}_{+}$ operator on the fractional stable set polytope to compute the stable set polytope). We introduce a generalized vertex-stretching operation that appears to be promising in generating \({{\,\textrm{LS}\,}}_+\) ${\text{LS}}_{+}$ -minimal graphs and study its properties. We also provide several new \({{\,\textrm{LS}\,}}_+\) ${\text{LS}}_{+}$ -minimal graphs, most notably the first known instances of 12-vertex graphs with \({{\,\textrm{LS}\,}}_+\) ${\text{LS}}_{+}$ -rank 4, which provides the first advance in this direction since Escalante, Montelar, and Nasini’s discovery of a 9-vertex graph with \({{\,\textrm{LS}\,}}_+\) ${\text{LS}}_{+}$ -rank 3 in 2006.