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. (author's abstract) ; Series: Preprint Series / Department of Applied Statistics and Data Processing

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

en

application/pdf

http://epub.wu.ac.at/898/1/document.pdf

Adapt according to the license agreement. Always reference the original source and author.