Relevant Cycles in Biopolymers and Random Graphs


Petra M. Gleiss and Peter F. Stadler

Fourth Slovene International Conference in Graph Theory
Bled, SLO, June 28 - July 2, 1999

Short cycles are an important characteristic of molecular graphs in organic chemistry as well as in structural biology. Minimum cycle bases are of particular interest, despite the fact that they are usually not unique. Hence, one sometimes resorts to the set relevant cycles, defined as the union of all minimum cycles bases. Here we introduce the set of essential cycles as the intersection of a graph's minimum cycle bases and provide an algorithm for their computation. Furthermore, we extend previous bounds on the length of minimal cycles bases to certain book-embeddable graphs.


Minimal Cycle Basis, Relevant Cycles, Essential Cycles, Biopolymer Graphs.

Return to 1999 working papers list.