Finding a shortest cycle in a subspace of the cycle space of a graph

摘要

Thomassen’s 3-path-condition shows that it is relatively easy for one to find a shortest cycle in a collection of cycles beyond a subspace of the cycle space of a connected graph and the real challenge is to find a shortest cycle contained in a given subspace of the cycle space of a graph. In this article we investigate the shorter cycle structures in a given subspace of a graph and find a set of cycles in a given graph containing much information about short cycles. We show that for a large range of subspaces of a graph satisfying a “parity condition”, there exists a polynomial time algorithm to find a shortest cycle in these subspaces. This makes a unified treatment of several famous algorithms. Finally we provide lower bounds of some types of short cycles in embedded graphs.