1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ What evidence do you have that the LTF for that graph has the form you describe? Numerical? Educated guesswork? Confirmation in special cases? $\endgroup$
    – Yemon Choi
    Nov 24, 2011 at 2:22
  • 1
    $\begingroup$ confirmation in special cases and educated guess work! It is of this form for cycle graphs!! $\endgroup$
    – Turbo
    Nov 24, 2011 at 4:12
  • 1
    $\begingroup$ 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. $\endgroup$ May 2, 2012 at 2:23
  • $\begingroup$ So professor Godsil do you think, this estimate could be on the right track? $\endgroup$
    – Turbo
    Aug 12, 2013 at 14:46

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ true but does that reduce to this is the question! $\endgroup$
    – Turbo
    Nov 24, 2011 at 19:16
0
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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