G: a cycle $A$ is a subcycle of cycle $B$ if there exists vertices $c$ and $d$ such that:
- $cd$ is an edge of $A$.
- $F$ is the resulting path of $A$ after removing the edge $cd$.
- $E$ is a path from $c$ to $d$ of length at least $2$, and the cycle $B$ consists of the edges in $E$ and $F$
In the graph consisting of edges:
1,3 (with vertices
are both subcycles of
A cycle is minimal if it has no subcycles.
Given a graph
G, what is the worst-case (maximum) number of minimal cycles it could have???
My thought is a complete graph would have each triplet of vertices a minimum cycle, therefore about
n^3 but I don't know if that's right
The computer science application of this is:
To compute a Hamiltonian cycle, you could first start with a minimum cycle and then see if you can replace an edge in the cycle with a path of length at least
2 (finding a cycle we're a subcycle of). If you do this over and and over get lucky each time, you will end up with a Hamiltonian cycle.