Families of locally separated Hamilton paths

2014/11/14 by Janos Korner, Korner, Janos, Angelo Monti +1
Computer Science · Mathematics · #05C35 #05C62 #05D99 #94A24 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #cs.IT #math.CO #math.IT #msc:05C35 #msc:05C62 #msc:05D99 #msc:94A24

paper · pdf · doi:10.48550/arxiv.1411.3902

In this version an error in the previous manuscript is corrected

arxiv created 2015/05/04 · arxiv updated 2015/05/05

Abstract

We improve by an exponential factor the lower bound of Korner 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 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.

Related

• Hamilton paths with lasting separation
• Families of graph-different Hamilton paths
• Path separation by short cycles
• Improved upper bounds on even-cycle creating Hamilton paths
• Hamilton path decompositions of complete multipartite graphs