Interchangeability of Relevant Cycles in Graphs
The set R of relevant cycles of a graph G is the union of its
minimum cycle bases. We introduce a partition of R such that
each cycle in a class W can be expressed as a sum of other
cycles in W and shorter cycles. It is shown that each minimum
cycle basis contains the same number of representatives of a given class
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.
Mathematics Subject Classification:
Primary: 05C38 (paths and cycles).
Secondary: 05C85 (graphic algorithms),
92D20 (protein sequences, DNA sequences),
minimum cycle basis, relevant cylces