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.
2025
26
2
1
28
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]
Macajova, E.; Mazzuoccolo, G.; Tabarelli, G.
File in questo prodotto:
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

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1411494
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact