Triangle-different Hamiltonian paths

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.

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