Counting Small Cycle Double Covers
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908405781757952 |
|---|---|
| author | Jooken, Jorik Seamone, Ben Zamfirescu, Carol T. |
| author_facet | Jooken, Jorik Seamone, Ben Zamfirescu, Carol T. |
| contents | A theorem due to Seyffarth states that every planar $4$-connected $n$-vertex graph has a cycle double cover (CDC) containing at most $n-1$ cycles (a "small" CDC). We extend this theorem by proving that, in fact, such a graph must contain linearly many small CDCs (in terms of $n$), and provide stronger results in the case of planar $4$-connected triangulations. We complement this result with constructions of planar $4$-connected graphs which contain at most polynomially many small CDCs. Thereafter we treat cubic graphs, strengthening a lemma of Hušek and Šámal on the enumeration of CDCs, and, motivated by a conjecture of Bondy, give an alternative proof of the result that every planar 2-connected cubic graph on $n > 4$ vertices has a CDC of size at most $n/2$. Our proof is much shorter and obtained by combining a decomposition based argument, which might be of independent interest, with further combinatorial insights. Some of our results are accompanied by a version thereof for CDCs containing no cycle twice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_10604 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counting Small Cycle Double Covers Jooken, Jorik Seamone, Ben Zamfirescu, Carol T. Combinatorics 05C38, 05C45, 05C10, 05C30 A theorem due to Seyffarth states that every planar $4$-connected $n$-vertex graph has a cycle double cover (CDC) containing at most $n-1$ cycles (a "small" CDC). We extend this theorem by proving that, in fact, such a graph must contain linearly many small CDCs (in terms of $n$), and provide stronger results in the case of planar $4$-connected triangulations. We complement this result with constructions of planar $4$-connected graphs which contain at most polynomially many small CDCs. Thereafter we treat cubic graphs, strengthening a lemma of Hušek and Šámal on the enumeration of CDCs, and, motivated by a conjecture of Bondy, give an alternative proof of the result that every planar 2-connected cubic graph on $n > 4$ vertices has a CDC of size at most $n/2$. Our proof is much shorter and obtained by combining a decomposition based argument, which might be of independent interest, with further combinatorial insights. Some of our results are accompanied by a version thereof for CDCs containing no cycle twice. |
| title | Counting Small Cycle Double Covers |
| topic | Combinatorics 05C38, 05C45, 05C10, 05C30 |
| url | https://arxiv.org/abs/2506.10604 |