# Is this general form of Lovasz theta function of circulant graphs?

Let $G$ be a cirulant graph with no loops at vertices and vertex degree $d$. Is the Lovasz theta function of this graph given by: $\vartheta(G) = \max_{i}\frac{-N\epsilon_{i}}{-\epsilon_{i}+d-1}$?

where $\epsilon_{i}$ are the eigenvalues of the adjacency matrix $A$ of the graph and is given by $\epsilon_{i} = 2\sum_{j=2}^{\frac{N-1}{2}}a_{j}cos(\frac{2\pi(j-1)i}{N})$ where $a_{j} \in \{0,1\}$ form the first row of $A$.

• What evidence do you have that the LTF for that graph has the form you describe? Numerical? Educated guesswork? Confirmation in special cases? Nov 24 '11 at 2:22
• confirmation in special cases and educated guess work! It is of this form for cycle graphs!!
– Mr.
Nov 24 '11 at 4:12
• I think the denominator in your formula should be $-\epsilon_i +d$. You bound is then equal to the Delsarte-Hoffman bound for the size of a coclique in a regular graph. May 2 '12 at 2:23
• So professor Godsil do you think, this estimate could be on the right track?
– Mr.
Aug 12 '13 at 14:46

Computing Lovasz $\theta$ for circulant graphs can be reduced to linear programming; this is well-known, I think (already mentioned in A.Schrijver's 1979 paper "A comparison of the Delsarte and Lovasz bounds"). Indeed, $A$ is an element of the Bose-Mesner algebra of the commutative associative scheme (obtained from the natural action of the dihedral group on $N$ points), and Schrijver shows that in this case $\theta$ can be found by simultaneous diagonalisation of all the basis elements of the algebra (in this case, it is the same as diagonalizing the (symmetric) circulant matrices) and solving the resulting linear program.