Graphs whose vertices are graphs with bounded degree: Distance problems

By an f-graph we mean a graph having no vertex of degree greater than f. Le t U(n, f) denote the graph whose vertex set is the set of unlabeled f-graph s of order n and such that the vertex corresponding to the graph G is adjac ent to the vertex corresponding to the graph H if and only if H is obtainab le from G by either the insertion or the deletion of a single edge. The dis tance between two graphs G and H of order n is defined as the least number of insertions and deletions of edges in G needed to obtain H. This is also the distance between two vertices in U(n, f). For simplicity, we also refer to the vertices in U(n, f) as the graphs in U(n, f). The graphs in U(n, f) are naturally grouped and ordered in levels by their number of edges. The distance [nf/2] from the empty graph to an f-graph having a maximum number of edges is called the height of U(n, f). For f = 2 and for f greater than or equal to (n - 1)/2, the diameter of U(n, f) is equal to the height. Howe ver, there are values of the parameters where the diameter exceeds the heig ht. We present what is known about the following two problems: (1) What is the diameter of U(n, f) when 3 less than or equal to f < (n - 1)/2? (2) For fixed f, what is the least value of n such that the diameter of U(n, f) ex ceeds the height of U(n, f)?