The theta function of a graph, also known as the Lov?sz number, hasthe 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 theexplicit value of the theta function for special classes of graphs. Inthis paper we provide the explicit formula for the Lov?sz number ofthe union of two cycles, in two special cases, and a practicallyefficient algorithm, for the general case.

On the Lovasz number of certain circulant graphs / V., Brimkov; B., Codenotti; V., Crespi; Leoncini, Mauro. - STAMPA. - 1767:(2000), pp. 291-305. ((Intervento presentato al convegno N/A tenutosi a N/A nel N/A.

On the Lovasz number of certain circulant graphs

LEONCINI, Mauro
2000

Abstract

The theta function of a graph, also known as the Lov?sz number, hasthe 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 theexplicit value of the theta function for special classes of graphs. Inthis paper we provide the explicit formula for the Lov?sz number ofthe union of two cycles, in two special cases, and a practicallyefficient algorithm, for the general case.
N/A
N/A
N/A
1767
291
305
V., Brimkov; B., Codenotti; V., Crespi; Leoncini, Mauro
On the Lovasz number of certain circulant graphs / V., Brimkov; B., Codenotti; V., Crespi; Leoncini, Mauro. - STAMPA. - 1767:(2000), pp. 291-305. ((Intervento presentato al convegno N/A tenutosi a N/A nel N/A.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/641689
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 8
social impact