On the Lovasz number of certain circulant graphs

Abstract

The theta function of a graph, also known as the Lovasz number, has the remarkable property of being computable in polynomial time, despite being sandwiched between two hard to compute integers, i.e., clique and chromatic number. Very little is known about the explicit value of the theta function for special classes of graphs. In this paper we provide the explicit formula for the Lovasz number of the union of two cycles, in two special cases, and a practically efficient algorithm, for the general case.