Multigraphs with Unique Partition into Cycles

Abstract

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 $\ge 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".

14 pages, 4 figures