When do short cycles generate the cycle space?
Let \(G=(V,E)\) be a graph with arbitrary (perturbed) edge weights and let C(e) denote the shortest cycle containing the edge e. It is easy to show that the cycles in \(\{\) C(e)\(| e\in E\}\) are not only independent (over GF(2)) but are also contained in the cycle basis of minimum weight. We characterize, in several ways, those graphs for which \(\{\) C(e)\(| e\in E\}\) is a cycle basis (hence, the cycle basis of minimum weight) for every perturbed edge weighting. For example, these are the planar graphs such that no dual graph has two non-adjacent nodes connected by three internally node disjoint paths. Another characterization shows that these graphs can be obtained from cycles, bonds and \(K_ 4's\) by a special type of 2-sum operation; this leads to a linear time recognition algorithm for this class.
- Generating cycle spaces for graphs on surfaces with small genera
- Is every cycle basis fundamental?
- Minimum Cycle Bases and Their Applications
- The prism-free planar graphs and their cycles bases
- RELEVANT CYCLES IN CHEMICAL REACTION NETWORKS
- Characterization of minimum cycle basis in weighted partial 2-trees
- Finding shorter cycles in a weighted graph
- Computing cyclic invariants for molecular graphs
- Sparse cycle bases for graphs with bounded genus
- Short cycle structure of graphs on surfaces. I: The uniqueness theorems
This page was built for publication: When do short cycles generate the cycle space?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757424)
