I noticed that Hamiltonian cycles, for graphs of a given number of vertices, form lattices, by adding cycles. They start with a single cycle and ending with a full set of lattices. What seems so interesting about that is that those are sublattices of a lattice of unlabelled Hamiltonian graphs, for graphs of a given number of vertices, by adding edges. Further, similar structures (that also partition HG) occur by adding vertices.

Let's back up a bit. I was trying to build a sublattice by adding Hamiltonian cycles. It is tricky because we would prefer to avoid labeled graphs. It seems tedious to define 'cycles' as equivalence classes of graphs that have the same cycles, but it works. Maybe universal algebra would be more convenient.

It should be easier to think of the next bigger lattice. Think of a circular graph at the top and the complete graph at the bottom. Since we can add edges in different places, we have a lattice. What seem important is that the 'cycles lattice' has to form a sublattice of the 'graph lattice'.
[add diagrams]

A similar pair of structures arises by adding vertices instead of adding edges. I have to clarify what I mean by ‘adding vertices’. We add vertices on Hamiltonian edges. That is, an edge, that is part of a Hamiltonian cycle, is replaced with two edges that each have an end connected to the vertices of the original edge and the other ends to the new vertex. The resulting structures are forests. Since an edge is added with each vertex, E - V is constant. Also, the degree of each vertex is preserved. That is how we can determine the roots of the trees.

Again, the substructure seems more interesting. We need to explain how we embed 'cycles' in our forests. Each tree tends to preserve cycles; except for complete graphs (at the roots), because of the change of size (and order) of the graphs. We also need to extend the equivalence class (of Hamiltonian cycles) once more to accommodate their change of size (to match the size of the graph).

The next larger structure is a combination, so that all Hamiltonian graphs are represented. It does not end there! We can add labeling. I know about group action and Polya's enumeration theorem, but I don't know how to do it over an algebraic structure to form another structure. Further, I would add walks on those graphs. Again, I'm not sure how to incorporate them into a structure.

I was trying to prove an asymptotic bound (polynomial) on a property of a portion (given by a rational function) of the elements of the structure. Maybe there is no need for the algebra because rational proportion should make things easy, maybe. The property to bound is the length of the depth first search walk. Walks are convenient. They preserve an invariant, while adding vertices, until H-cycles decrease. Also, non-greedy algorithms won't work for the property.
[add links to pnp]