Approximate cycle double cover
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917071312388096 |
|---|---|
| author | Ghanbari, Babak Šámal, Robert |
| author_facet | Ghanbari, Babak Šámal, Robert |
| contents | The Cycle double cover (CDC) conjecture states that for every bridgeless graph $G$, there exists a family $\mathcal{F}$ of cycles such that each edge of the graph is contained in exactly two members of $\mathcal{F}$. Given an embedding of a graph~$G$, an edge $e$ is called a \emph{singular edge} if it is visited twice by the boundary of one face. The CDC conjecture is equivalent to bridgeless cubic graphs having an embedding with no singular edge. In this work, we introduce nontrivial upper bounds on the minimum number of singular edges in an embedding of a cubic graph. Moreover, we present efficient algorithms to find embeddings satisfying these bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_07285 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximate cycle double cover Ghanbari, Babak Šámal, Robert Combinatorics Computational Complexity Discrete Mathematics The Cycle double cover (CDC) conjecture states that for every bridgeless graph $G$, there exists a family $\mathcal{F}$ of cycles such that each edge of the graph is contained in exactly two members of $\mathcal{F}$. Given an embedding of a graph~$G$, an edge $e$ is called a \emph{singular edge} if it is visited twice by the boundary of one face. The CDC conjecture is equivalent to bridgeless cubic graphs having an embedding with no singular edge. In this work, we introduce nontrivial upper bounds on the minimum number of singular edges in an embedding of a cubic graph. Moreover, we present efficient algorithms to find embeddings satisfying these bounds. |
| title | Approximate cycle double cover |
| topic | Combinatorics Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2511.07285 |