In graph 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$
For example:
In the graph consisting of edges: 1,2
2,3
3,4
4,1
1,3
(with vertices 1
-4
), then:
3,4
4,1
1,3
and
1,2
2,3
1,3
are both subcycles of
1,2
2,3
3,4
4,1
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.