Interchangeability of Relevant Cycles in Graphs


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.


Minimum Cycle Basis, Relevant Cycles

AMS Subject Classification

Primary 05C38.
Secondary 05C85, 92D20, 92E10.

Return to 1999 working papers list.