A construction of Alon and Krivelevich gives highly pseudorandom Kk-free graphs on n vertices with edge density equal to Θ(n−1=(k−2)). In this short note we improve their result by constructing an infinite family of highly pseudorandom Kk-free graphs with a higher edge density of Θ(n−1=(k−1)).
A construction for clique-free pseudorandom graphs / Bishnoi, A.; Ihringer, F.; Pepe, V.. - In: COMBINATORICA. - ISSN 0209-9683. - 40:3(2020), pp. 307-314. [10.1007/s00493-020-4226-6]
A construction for clique-free pseudorandom graphs
Pepe V.
2020
Abstract
A construction of Alon and Krivelevich gives highly pseudorandom Kk-free graphs on n vertices with edge density equal to Θ(n−1=(k−2)). In this short note we improve their result by constructing an infinite family of highly pseudorandom Kk-free graphs with a higher edge density of Θ(n−1=(k−1)).File allegati a questo prodotto
| File | Dimensione | Formato | |
|---|---|---|---|
|
Bishnoi_Constructioncliquefree_2020.pdf
solo gestori archivio
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
260.21 kB
Formato
Unknown
|
260.21 kB | Unknown | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
