کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4626345 | 1631786 | 2015 | 6 صفحه PDF | دانلود رایگان |
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.
Journal: Applied Mathematics and Computation - Volume 268, 1 October 2015, Pages 393–398