Finding Shorter Cycles in a Weighted Graph.

In this paper we investigate the structures of short cycles in a weighted graph. By Thomassen's $$3$$ -path-condition theory (Thomassen in J Comb Theory Ser 48:155-177, ), it is easy to find a shortest cycle in a collection of cycles beyond a subspace of the cycle space of a graph. What is more difficult for one to do is to find a shortest cycle within a subspace of the cycle space in polynomial time. By using the Dijkstra's algorithm (Dijkstra in Numer Math 1:55-61, ) we find a collection $$\mathcal {C}$$ of cycles containing many types of short cycles within a given subspace of the cycle space of a graph and this implies a polynomial time algorithm (called extended fundamental cycle algorithm) to locate all the possible shortest cycles in a weighted graph. In the case of unweighted graphs, the algorithm may also find every shortest even cycle in a graph, this greatly improved a result of Grötschel and Pulleyblank (Oper Res Lett 1:23-27, ), Monien (Computing 31:355-369, ), Yuster and Zwick (SIAM J Discrete Math 10:209-222, ). In fact, our algorithm shows that there are at most $$O(n^4)$$ many such short cycles in an unweighted graph of order $$n$$ . Further more, our fundamental cycle method may find a minimum cycle base (or simply MCB as some scholars named) in the cycle space of a graph. Since the structure of MCB's is unique (Ren and Deng in Discrete Math 307:2654-2660, ), this shows that, in the sense, cycles in a MCB are nearly-fundamental (i.e., each element in a MCB is a sum of at most two fundamental cycles). This provides a new way to study MCB. [ABSTRACT FROM AUTHOR]