Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2307.06649 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910856024948736 |
|---|---|
| author | Fischer, Jens Walter |
| author_facet | Fischer, Jens Walter |
| contents | The cycle double cover conjecture is a long standing problem in graph theory, which links local properties, the valency of a vertex and no bridges, and a global property of the graph, being covered by a particular set of cycles. We prove the conjecture using a lift of walks and cycles in $G$ to sets of open and closed edges on $\mathcal{L}(\mathcal{L}(G))$, the line graph of the line graph of $G$. We exploit that triangles are preserved by the line graph operator to obtain a one-to-one mapping from walks in the underlying graph $G$ to walks on $\mathcal{L}(\mathcal{L}(G))$. We prove that each set of "double walk covers" in $G$ induces a certain set of $\lbrace 0,1\rbrace$ labels on a subgraph covering of $\mathcal{L}(\mathcal{L}(G))$, minus a set of triangles, and conversely, that there is such a set of labels such that its projection back to $G$ implies a double cycle cover, if $G$ is an simple bridgeless triangle-free cubic graph. The techniques applied are inspired by percolation theory, flipping the $\lbrace 0,1\rbrace$ labels to obtain the desired structure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_06649 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The cycle double cover conjecture from the perspective of percolation theory on iterated line graphs Fischer, Jens Walter Combinatorics The cycle double cover conjecture is a long standing problem in graph theory, which links local properties, the valency of a vertex and no bridges, and a global property of the graph, being covered by a particular set of cycles. We prove the conjecture using a lift of walks and cycles in $G$ to sets of open and closed edges on $\mathcal{L}(\mathcal{L}(G))$, the line graph of the line graph of $G$. We exploit that triangles are preserved by the line graph operator to obtain a one-to-one mapping from walks in the underlying graph $G$ to walks on $\mathcal{L}(\mathcal{L}(G))$. We prove that each set of "double walk covers" in $G$ induces a certain set of $\lbrace 0,1\rbrace$ labels on a subgraph covering of $\mathcal{L}(\mathcal{L}(G))$, minus a set of triangles, and conversely, that there is such a set of labels such that its projection back to $G$ implies a double cycle cover, if $G$ is an simple bridgeless triangle-free cubic graph. The techniques applied are inspired by percolation theory, flipping the $\lbrace 0,1\rbrace$ labels to obtain the desired structure. |
| title | The cycle double cover conjecture from the perspective of percolation theory on iterated line graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2307.06649 |