2025/04/10 by Cooper, Joshua, Okur, Utku · 1 citation
#05C20 #05C38 #Combinatorics (math.CO) #FOS: Mathematics #Primary 05C75 #Secondary 05C45
paper · doi:10.48550/arxiv.2504.08083
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 S, ``bridgeless cactus multigraphs", elements of which are obtained by replacing every edge of a tree with a cycle of length ≥ 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 S, namely, ``Christmas cactus digraphs".