New bounds for the number of lightest cycles in undirected graphs

Consider an undirected graph G=(V,E) with positive integer edge weights. Subramanian [11] established an upper bound of |V|⁴/6 on the number of minimum weight cycles. We present a new algorithm to enumerate all minimum weight cycles with a complexity of O(|V|³(|E|+|V|log⁡|V|)). Using this algorithm, we derive the following upper bounds for the number of minimum weight cycles: if the minimum weight is even, the bound is |V|⁴/4, and if it is odd, the bound is |V|³/2. Notably, we improve Subramanian's bound by an order of magnitude when the minimum weight of a cycle is odd. Additionally, we demonstrate that these bounds are asymptotically tight.