It is known that smallest counterexamples to the Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture (if they exist) are cyclically 4- and 5-edge-connected, respectively. We further analyse small cycle separating cuts in possible counterexamples. We prove that if a smallest counterexample G to the CDC Conjecture contains a cycle separating 4-cut S, then the behaviour of the admissible CDC coverings along the dangling edges of the two 4-poles induced by S is uniquely determined among more than 219 a priori possibilities. Similarly, for the Berge-Fulkerson Conjecture, we prove that among more than 2111 a priori possibilities, there are only 13 pairs of admissible sets that could occur along the dangling edges of a 5-cut in a smallest counterexample.
Cycle separating cuts in possible counterexamples to the cycle double cover and the Berge-Fulkerson conjectures / Macajova, E., Mazzuoccolo, G., Tabarelli, G.. - In: ARS MATHEMATICA CONTEMPORANEA. - ISSN 1855-3966. - 26:2(2025), pp. 1-28. [10.26493/1855-3974.3409.c13]
Cycle separating cuts in possible counterexamples to the cycle double cover and the Berge-Fulkerson conjectures
Mazzuoccolo G.;Tabarelli G.
2025
Abstract
It is known that smallest counterexamples to the Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture (if they exist) are cyclically 4- and 5-edge-connected, respectively. We further analyse small cycle separating cuts in possible counterexamples. We prove that if a smallest counterexample G to the CDC Conjecture contains a cycle separating 4-cut S, then the behaviour of the admissible CDC coverings along the dangling edges of the two 4-poles induced by S is uniquely determined among more than 219 a priori possibilities. Similarly, for the Berge-Fulkerson Conjecture, we prove that among more than 2111 a priori possibilities, there are only 13 pairs of admissible sets that could occur along the dangling edges of a 5-cut in a smallest counterexample.| File | Dimensione | Formato | |
|---|---|---|---|
|
amc_3409.pdf
Open access
Tipologia:
VOR - Versione pubblicata dall'editore
Licenza:
[IR] creative-commons
Dimensione
412.02 kB
Formato
Adobe PDF
|
412.02 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate

I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris




