We improve by an exponential factor the lower bound of K¨orner and Muzi for the cardinality of the largest family of Hamilton paths in a complete graph of n vertices in which the union of any two paths has maximum degree 4. The improvement is through an explicit construction while the previous bound was obtained by a greedy algorithm. We solve a similar problem for permutations up to an exponential factor.
Families of locally separated Hamilton paths / Körner, János; Monti, Angelo. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - STAMPA. - (2018), pp. 402-410. [10.1002/jgt.22220]
Families of locally separated Hamilton paths
Körner, János;Monti, Angelo
2018
Abstract
We improve by an exponential factor the lower bound of K¨orner and Muzi for the cardinality of the largest family of Hamilton paths in a complete graph of n vertices in which the union of any two paths has maximum degree 4. The improvement is through an explicit construction while the previous bound was obtained by a greedy algorithm. We solve a similar problem for permutations up to an exponential factor.File allegati a questo prodotto
| File | Dimensione | Formato | |
|---|---|---|---|
|
Monti_postprint_Families_2017.pdf
accesso aperto
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
223.45 kB
Formato
Adobe PDF
|
223.45 kB | Adobe PDF | |
|
Monti_Families_2017.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
168.89 kB
Formato
Adobe PDF
|
168.89 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
