Families of Graph-different Hamilton Paths

Authors:
  • JKJános Körner
    János Körner
  • SMSilvia Messuti
    Silvia Messuti
  • GSGábor Simonyi
    Gábor Simonyi

Abstract
Let $\mathbb{D}\subseteq \mathbb{N}$ be an arbitrary subset of the natural numbers. For every n, let $M(n, \mathbb{D})$ be the maximum of the cardinality of a set of Hamiltonian paths in the complete graph $K_n$ such that the union of any two paths from the family contains a not necessarily induced cycle of some length from $\mathbb{D}$. We determine or bound the asymptotics of $M(n, \mathbb{D})$ in various special cases. This problem is closely related to that of the permutation capacity of graphs and constitutes a further extension of the problem area around Shannon capacity. We also discuss how to generalize our cycle-difference problems and present an example where cycles are replaced by 4-cliques. These problems are in a natural duality to those of graph intersection, initiated by Erdős, Simonovits, and Sós. The lack of kernel structure as a natural candidate for optimum makes our problems quite challenging.

This publication has 5 references indexed in Scilit: