## 99-07-046

#
Abstract:

Interchangeability of Relevant Cycles in Graphs

[PostScript]

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

Submitted to: *Electronic J. Combinatorics*

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.

### Keyword

Minimum Cycle Basis, Relevant Cycles

### AMS Subject Classification

Primary 05C38.

Secondary 05C85, 92D20, 92E10.

Return to 1999 working papers list.