0
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

If I understand correctly, you call a cycle "minimum" if it has no chord.

Then the number of minimum cycles can be exponential. As an example, start from a graph containing a single cycle $C$ and replace each edge $e = (u,v)$ with two "split" vertices $x_e, y_e$ and the edges $(u, x_e), (x_e,v), (u, y_e), (y_e,v)$.

Notice that, once you choose one of $x_e$ and $y_e$ for each edge $e$, you can build a chordless cycle that traverses exactly all original vertices of $C$ and all the chosen split vertices.

The resulting graph has $3n$ vertices and $2^{n}$ minimum cycles.

Here is an example of one such graph:

example

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.