Interchangeability of relevant cycles in graphs (Q1972676)

Summary: The set \(\mathcal{R}\) of relevant cycles of a graph \(G\) is the union of its minimum cycle bases. We introduce a partition of \(\mathcal{R}\) such that each cycle in a class \(\mathcal{W}\) can be expressed as a sum of other cycles in \(\mathcal{W}\) and shorter cycles. It is shown that each minimum cycle basis contains the same number of representatives of a given class \(\mathcal{W}\). This result is used to derive upper and lower bounds on the number of distinct minimum cycle bases. Finally, we give a polynomial-time algorithm to compute this partition.