When Do Short Cycles Generate the Cycle Space?

✍ Scribed by D. Hartvigsen; R. Mardon

• Book ID: 102587406
• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 471 KB
• Volume: 57
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1993.1008

✦ Synopsis

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) \mid e \in E}) are not only independent (over (G F(2))) but are also contained in the cycle basis of minimum weight. We characterize, in several ways, those graphs for which ({C(e) \mid 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 nodedisjoint 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. " 1993 Academic Press. Inc.