HAMILTON PATHS IN GRAPHS WHOSE VERTICES ARE GRAPHS

摘要

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.