On the Lovasz number of certain circulant graphs

Simple item page
dc.contributor.authorBrimkov, VE
dc.contributor.authorCodenotti, B
dc.contributor.authorCrespi, V
dc.contributor.authorLeoncini, M
dc.date.accessioned2026-02-06T18:17:28Z
dc.date.issued2000
dc.departmentDoğu Akdeniz Üniversitesi
dc.description4th Italian Conference on Algorithms and Complxity (CIAC 2000) -- MAR 01-03, 2000 -- UNIV ROME LA SAPIENZA, ROME, ITALY
dc.description.abstractThe theta function of a graph, also known as the Lovasz number, has the remarkable property of being computable in polynomial time, despite being sandwiched between two hard to compute integers, i.e., clique and chromatic number. Very little is known about the explicit value of the theta function for special classes of graphs. In this paper we provide the explicit formula for the Lovasz number of the union of two cycles, in two special cases, and a practically efficient algorithm, for the general case.
dc.description.sponsorshipBanca Credito Cooperat Roma,Univ Roma, La Sapienza, Dept Sci Informaz,European Assoc Theoret Comp Sci,Grp Nazl Informat Matemat,Italsoft Ingegneria Sistemi Srl,Univ Studi Roma, La Sapienza,Univ Studi Roma, Tor Vergata
dc.identifier.endpage305
dc.identifier.isbn3-540-67159-5
dc.identifier.issn0302-9743
dc.identifier.scopusqualityQ3
dc.identifier.startpage291
dc.identifier.urihttps://hdl.handle.net/11129/9000
dc.identifier.volume1767
dc.identifier.wosWOS:000165334400024
dc.identifier.wosqualityN/A
dc.indekslendigikaynakWeb of Science
dc.language.isoen
dc.publisherSpringer-Verlag Berlin
dc.relation.ispartofAlgorithms and Complexity
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/openAccess
dc.snmzKA_WoS_20260204
dc.subjectCapacity
dc.titleOn the Lovasz number of certain circulant graphs
dc.typeConference Object

Files

Collections

WoS Indexed Publications Collection