The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is...

We characterize the distributions of short cycles in a large metabolic network previously shown to have small world characteristics and a power law degree distribution. Compared with three classes of random networks, including Erdős–Rényi random graphs and synthetic small world networks of...

We characterize the distributions of short cycles in a large metabolic network previously shown to have small world characteristics and a power law degree distribution. Compared with three networks of the same connectivity, the metabolic network has a particularly large number of triangles and a...

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

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 and W and shorter cycles. It is shown that each minimum cycle basis contains the same number of...