MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
What evidence do you have that the LTF for that graph has the form you describe? Numerical? Educated guesswork? Confirmation in special cases? – Yemon Choi Nov 24 '11 at 2:22
confirmation in special cases and educated guess work! It is of this form for cycle graphs!! – Turbo 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. – Chris Godsil May 2 '12 at 2:23
So professor Godsil do you think, this estimate could be on the right track? – Turbo 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.

share|cite|improve this answer
true but does that reduce to this is the question! – Turbo Nov 24 '11 at 19:16

No. In the case of the circulant graph of 2n vertices C(1,n) i.e., the Möbius Ladder, we obtain a division by zero in the calculus.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.