Multigraphs with Unique Partition into Cycles
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915236801413120 |
|---|---|
| author | Cooper, Joshua Okur, Utku |
| author_facet | Cooper, Joshua Okur, Utku |
| contents | Due to Veblen's Theorem, if a connected multigraph $X$ has even degrees at each vertex, then it is Eulerian and its edge set has a partition into cycles. In this paper, we show that an Eulerian multigraph has a unique partition into cycles if and only if it belongs to the family $\mathcal{S}$, ``bridgeless cactus multigraphs", elements of which are obtained by replacing every edge of a tree with a cycle of length $\geq 2$. Other characterizing conditions for bridgeless cactus multigraphs and digraphs are provided.
Furthermore, for a digraph $D$, we list conditions equivalent to having a unique Eulerian circuit, thereby generalizing a previous result of Arratia-Bollobás-Sorkin. In particular, we show that digraphs with a unique Eulerian circuit constitute a subfamily of $\mathcal{S}$, namely, ``Christmas cactus digraphs". |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_08083 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multigraphs with Unique Partition into Cycles Cooper, Joshua Okur, Utku Combinatorics Primary 05C75, Secondary 05C45, 05C38, 05C20 Due to Veblen's Theorem, if a connected multigraph $X$ has even degrees at each vertex, then it is Eulerian and its edge set has a partition into cycles. In this paper, we show that an Eulerian multigraph has a unique partition into cycles if and only if it belongs to the family $\mathcal{S}$, ``bridgeless cactus multigraphs", elements of which are obtained by replacing every edge of a tree with a cycle of length $\geq 2$. Other characterizing conditions for bridgeless cactus multigraphs and digraphs are provided. Furthermore, for a digraph $D$, we list conditions equivalent to having a unique Eulerian circuit, thereby generalizing a previous result of Arratia-Bollobás-Sorkin. In particular, we show that digraphs with a unique Eulerian circuit constitute a subfamily of $\mathcal{S}$, namely, ``Christmas cactus digraphs". |
| title | Multigraphs with Unique Partition into Cycles |
| topic | Combinatorics Primary 05C75, Secondary 05C45, 05C38, 05C20 |
| url | https://arxiv.org/abs/2504.08083 |