Finding a shortest cycle in a subspace of the cycle space of a graph》.pdfVIP

Applied Mathematics and Computation 268 (2015) 393–398 Contents lists available at ScienceDirect Applied Mathematics and Computation journal homepage: /locate/amc Finding a shortest cycle in a subspace of the cycle space of a graph a,b,∗ b b Fugang Chao , Han Ren , Ni Cao a Department of Mathematics, Shanghai University, Shanghai 200444, P.R. China b Department of Mathematics, East China Normal University, Shanghai 200062, P.R. China a r t i c l e i n f o a b s t r a c t Keywords: Thomassen’s 3-path-condition shows that it is relatively easy for one to find a shortest cycle 3-path-condition in a collection of cycles beyond a subspace of the cycle space of a connected graph and the BFS tree real challenge is to find a shortest cycle contained in a given subspace of the cycle space of a Short cycle graph. In this article we investigate the shorter cycle structures in a given subspace of a graph Embedded 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 ty