Algorithmic and explicit determination of the Lovász number for certain circulant graphs

We consider the problem of computing the Lovász theta function for circulant graphs Cn,JCn,J of degree four with nn vertices and chord length JJ, 2⩽J⩽n2⩽J⩽n. We present an algorithm that takes O(J)O(J) operations if JJ is an odd number, and O(n/J)O(n/J) operations if JJ is even. On the considered class of graphs our algorithm strongly outperforms the known algorithms for theta function computation. We also provide explicit formulas for the important special cases J=2J=2 and J=3J=3.