Interchangeability of Relevant Cycles in Graphs

Petra M. Gleiss, Josef Leydold, and Peter F. Stadler


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), 92E10.

Keywords: minimum cycle basis, relevant cylces

Download Paper   PostScript | PDF      [EJC]