Families of locally separated Hamilton paths

DOI10.1002/JGT.22220MaRDI QIDQ4581272zbMATH OpenOpenAlexFDO

Authors János Körner, Angelo Monti

Publication date 16 August 2018

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

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

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)

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.

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

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)