Hamilton Paths in Graphs Whose Vertices are Graphs

Abstract

Let $U(n,f)$ denote the graph with vertex set the set of unlabeled graphs of order $n$ that have no vertex of degree greater than $f$. Two vertices $H$ and $G$ of $U(n,f)$ are adjacent if and only if $H$ and $G$ differ (up to isomorphism) by exactly one edge. The problem of determining the values of $n$ and $f$ for which $U(n,f)$ contains a Hamilton path is investigated. There are only a few known non-trivial cases for which a Hamilton path exists. Specifically, these are $U(5,3)$, $U(6,3)$, and $U(7,3)$. On the other hand, there are many cases for which it is shown that no Hamilton path exists. The complete solution of this problem is unresolved.