|
1
|
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$. |
|||||||||||
|
|
0
|
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. |
||
|
|
|
2
|
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. |
|||
|
