Families of locally separated Hamilton paths

DOI10.1002/JGT.22220zbMATH Open1393.05172arXiv1411.3902OpenAlexW2963665681MaRDI QIDQ4581272FDOQ4581272

Authors: János Körner, Angelo Monti 

Publication date: 16 August 2018

Published in: Journal of Graph Theory (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1411.3902

Recommendations

• Path separation by short cycles
• Families of very different paths
• Families of graph-different Hamilton paths
• New bounds on even cycle creating Hamiltonian paths using expander graphs
• Constructions via Hamiltonian theorems

zbMATH Keywords

permutationsHamilton pathsintersection problemsgraph-difference

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (9)

• Triangle-different Hamiltonian paths
• Improved upper bounds on even-cycle creating Hamilton paths
• New bounds on even cycle creating Hamiltonian paths using expander graphs
• Families of graph-different Hamilton paths
• Path separation by short cycles
• On \(k\)-neighbor separated permutations
• Even cycle creating paths
• Constructions via Hamiltonian theorems
• Non-permitted journeys and Hamiltonian paths

This page was built for publication: Families of locally separated Hamilton paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581272)