The Wheels of the Orthogonal Latin Squares Polytope: Classification and Valid Inequalities

A wheel in a graph G(V,E) is an induced subgraph consisting of an odd hole and an additional node connected to all nodes of the hole. In this paper, we study the wheels of the intersection graph of the Orthogonal Latin Squares polytope (P_I). Our work builds on structural properties of wheels which are used to categorise them into a number of collectively exhaustive classes. These classes give rise to families of inequalities that are valid for P_I and facet-defining for its set-packing relaxation. The classification introduced allows us to establish the cardinality of the whole wheel class and determine the range of the coefficients of any variable included in a lifted wheel inequality. Finally, based on this classification, a constant-time recognition algorithm for wheel-inducing circulant matrices, is introduced.