BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR2002-438
ENTRY:: November 21, 2002
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Exact formulae for the Lovasz Theta Function of sparse Circulant Graphs
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Crespi, Valentino
DATE:: November 2002
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: Compressed Postscript at http://www.cs.dartmouth.edu/reports/TR2002-438.ps.Z
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR2002-438.pdf
ABSTRACT:: 
  The Lovasz theta function has attracted a lot of attention for its
connection with diverse issues, such as communicating without errors
and computing large cliques in graphs. Indeed this function enjoys the
remarkable property of being computable in polynomial time, despite
being sandwitched between clique and chromatic number, two well known
hard to compute quantities.
  In this paper I provide a closed formula for the Lovasz function of a
specific class of sparse circulant graphs thus generalizing Lovasz
results on cycle graphs (circulant graphs of degree 2).
END:: ncstrl.dartmouthcs//TR2002-438