Triangle-different Hamiltonian paths

2016/08/18 by István Kovács, Kovács, István, Dániel Soltész +1
Mathematics · #05C35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35

paper · pdf · doi:10.48550/arxiv.1608.05237

We slightly changed the introduction, added two more papers as references, and added a new short section which deals with the two related questions where Hamiltonian paths are replaced with arbitrary graphs and trees

arxiv created 2016/10/11 · arxiv updated 2016/10/13

Abstract

Let G be a fixed graph. Two paths of length n-1 on n vertices (Hamiltonian paths) are G-different if there is a subgraph isomorphic to G in their union. In this paper we prove that the maximal number of pairwise triangle-different Hamiltonian paths is equal to the number of balanced bipartitions of the ground set, answering a question of Körner, Messuti and Simonyi.

Related

• Families of graph-different Hamilton paths
• On a conjecture of Faudree and Schelp
• Hamilton paths with lasting separation
• Graphs with Many Hamiltonian Paths
• Families of locally separated Hamilton paths