IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishGiven an undirected graph G, let P-G(z) be the polynomial P-G(z) = Sigma(n)(-1)(n)c(n)z(n), where c(n) is the number of cliques of size n in G. We show that, for every G, the polynomial P-G(z) has only one root of smallest modulus. Clique polynomials are related to trace monoids. Indeed, 1/P-G(z) is the generating function of the sequence {t(n)}, where t(n) is the number of traces of size n in the trace monoid defined by G. Our result can be applied to derive asymptotic expressions for {t(n)} and other sequences arising from the analysis of algorithms for the recognition of trace languages.
Clique polynomials have a unique root of smallest modulus / M. Goldwurm, M. Santini. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 75:3(2000), pp. 127-132.
| Titolo: | Clique polynomials have a unique root of smallest modulus | |
| Autori: | GOLDWURM, MASSIMILIANO (Primo) SANTINI, MASSIMO (Ultimo) | |
| Parole Chiave: | clique polynomials ; formal languages ; graphs ; rational functions ; trace monoids | |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica | |
| Data di pubblicazione: | 2000 | |
| Rivista: | ||
| Tipologia: | Article (author) | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/S0020-0190(00)00086-7 | |
| Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
Pubblicazioni consigliate
http://hdl.handle.net/2434/19733
Copyright © 2022