This work confirms Voss's conjecture on bridges in cycles, suggesting that their total length is limited by the cycle's length.
Bridges are a classical concept in structural graph theory and play a fundamental role in the study of cycles. A conjecture of Voss from 1991 asserts that if disjoint bridges B₁, B₂, …, Bₖ of a longest cycle L in a $2$-connected graph overlap in a tree-like manner (i.e., induce a tree in the { overlap graph} of L), then the total { length} of these bridges is at most half the length of L. Voss established this for k ≤ 3 and used it as a key tool in his 1991 monograph on cycles and bridges. In this paper, we confirm the conjecture in full via a reduction to a cycle covering problem.
No takes yet. Share an insight, caveat, or question.
Ma et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: