Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G. Appa, D. Magos, I. Mourtos, and J.C.M. Janssen, “Clique facets of the orthogonal Latin squares polytope,” Research Report: LSE-CDAM-2001-04, London, 2001 (url: http://www.cdam.lse.ac.uk/Reports/Files/cdam-2001-04.pdf).
G. Appa, D. Magos, and I. Mourtos, “Properties and classification of the wheels of the OLS polytope,” Research Report: LSE-CDAM-2003-04, London, 2003 (url: http://www.cdam.lse.ac.uk/Reports/Files/cdam-2003-04.pdf).
F. Barahona and A.R. Mahjoub, “Compositions of graphs and polyhedra II: Stable sets,” SIAM J. Discrete Math., vol. 7, pp. 359–371, 1994.
E. Cheng and W.H. Cunningham, “Wheel inequalities for stable set polytopes,” Math. Program., vol. 77, pp. 389–421, 1997.
E. Cheng and S. de Vries, “Antiweb-wheel inequalities and their separation problems over the stable set polytopes,” Math. Program. vol. 92, pp. 153–175, 2002.
G.B. Dantzig, Linear Programming and Extensions, Princeton University Press: Princeton, NJ, 1963.
R. Euler, R.E. Burkard, and R. Grommes, “On Latin squares and the facial structure of related polytopes,” Discrete Math., vol. 62, pp. 155–181, 1986.
M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization (2nd corr. edition), Springer: Berlin, 1993.
C.F. Laywine and G.L. Mullen, Discrete Mathematics Using Latin Squares, John Wiley & Sons: New York, 1998.
M.W. Padberg, “On the facial structure of the set packing polyhedra,” Math. Program. vol. 5, pp. 199–215, 1973.
D.B. West, Introduction to Graph Theory (2nd ed.), Prentice-Hall: Englewood Cliffs, NJ, 2000.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Appa, G., Magos, D. & Mourtos, I. The Wheels of the Orthogonal Latin Squares Polytope: Classification and Valid Inequalities. J Comb Optim 10, 365–389 (2005). https://doi.org/10.1007/s10878-005-4924-4
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10878-005-4924-4