1
$\begingroup$

Given a connected graph with minimum degree 3 and a set of edges in this graph, I wish to find the number of decompositions of this edge set into cycles of the graph. I use decompositions in the sense that an edge in the set can be part of multiple cycles that the set is decomposed into. I know that this edge set is constructed by taking the union (not disjoint) of cycles of the graph, but I want to know how many other possible sets of cycles I could have taken the union of to get the same edge set. This might not be analytically possible but an algorithm to do this would be awesome.

  • 0
    You're after an [edge cycle cover](http://en.wikipedia.org/wiki/Edge_cycle_cover) of your graph (rather than a "decomposition").2012-11-01

0 Answers 0