In this paper we prove a Faber-Krahn-type inequality for regular trees and give a complete characterization of extremal trees. The main tools are rearrangements and perturbation of regular trees.

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

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

Two-connected outerplanar graphs have a unique minimal cycle basis with length $2|E|-|V|$. They are the only Hamiltonian graphs with a cycle basis of this length.