Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-2003-04 March 2003

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 column intersection graph of the OLS polytope (P_I). These structures induce valid inequalities for this polytope, which are facet defining for its set packing relaxation. Our work builds on simple structural properties of wheels which are used to categorise them into a number of collectively exhaustive classes. Each such class gives rise to a set of valid inequalities for P_I . Moreover, this classification allows us to estimate the cardinality of the whole wheel class as well as to derive a recognition algorithm for the circulant matrices corresponding to wheels of a particular type.

In a forthcoming paper, we show for some of the wheel classes presented here that they give rise to facet-defining inequalities for P_I.

A PDF file (345 kB) with the full contents of this report can be downloaded by clicking here (minor corrections added May 27 2003).

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2003-04, together with your name and postal address to:

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7732. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html