Interchangeability of Relevant Cycles in Graphs

Abstract

The set ${\cal R}$ of relevant cycles of a graph $G$ is the union of its minimum cycle bases. We introduce a partition of ${\cal R}$ such that each cycle in a class ${\cal W}$ can be expressed as a sum of other cycles in ${\cal W}$ and shorter cycles. It is shown that each minimum cycle basis contains the same number of representatives of a given class ${\cal 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.