99-07-26.pmg-ley-pfs
#
Interchangeability of Relevant Cycles in Graphs

### Abstract

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]

Erratum

Josef.Leydold@statistik.wu-wien.ac.at