## 99-07-042

#
Abstract:

Relevant Cycles in Biopolymers and Random Graphs

[PostScript]

##
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.

### Keyword

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

Return to 1999 working papers list.