On the facets and diameter of the k-cycle polytope

Abstract

We consider the k-cycle polytope which is the convex hull of the incidence vectors of simple cycles of fixed length k in a complete undirected graph. We summarize the previous results of Kovalev, Maurras, Nguyen and Vaxès (Maurras, J.-F., Kovalev, M.M. and Vaxès, Y., 2003, On the convex hull of the 3-cycle of the complete graph. Pesquisa Operacional, 23, 99–109; Maurras, J.-F. and Nguyen, V.H., 2000, The k-cycle polytope: 2. facets, Technical Report 359, Laboratoire d’Informatique de Marseille (LIM), Université de la Méditerranée; Maurras, J.-F. and Nguyen, V.H., 2001, On the linear description of the k-cycle polytope. International Transactions in Operational Research, 8 673–692 and Maurras, J.-F. and Nguyen, V.H., 2002, On the linear description of the 3-cycle polytope. European Journal of Operational Research, 137, 310–325.), and present new facet classes for the 3-cycle polytope along with a matroid approach to prove that a supporting inequality induces facet. We generalize the regular path inequalities introduced by Naddef and Rinaldi for the travelling salesman polytope, to the case of the k-cycle polytope and give an upper bound of 5 for the diameter of the k-cycle polytope.

Keywords:

• k-Cycle polytope
• Travelling salesman polytope
• Facets
• Adjacency
• Diameter

Keywords:

• 2000 Mathematics Subject Classification: 90C57

Acknowledgements

The authors are thankful to the anonymous referees for the many helpful comments and to Andreas Drexl for proof-reading parts of this article. The research of M.K. was partially supported by INTAS under grant number INTAS 03-51-5501.