×

zbMATH — the first resource for mathematics

On the Lovász number of certain circulant graphs. (English) Zbl 0955.05097
Bongiovanni, Giancarlo (ed.) et al., Algorithms and complexity. 4th Italian conference, CIAC 2000, Rome, Italy, March 1-3, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1767, 291-305 (2000).
The Lovász number (the theta function) of circulant graphs is studied. A linear programming formulation and a geometric approach are used. In the case of the union of two cycles either an explicit formula or an efficient algorithm are given.
For the entire collection see [Zbl 0933.00042].

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
94A40 Channel models (including quantum) in information and communication theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Software:
SDPpack
PDF BibTeX XML Cite