@Journal Article{Summon-FETCH-arxiv_primary_1708_091413,
title = {Cycle Decompositions and Constructive Characterizations},
author = {Heinrich, Irene} and {Streicher, Manuel},
year = {2017},
keywords ={Mathematics - Combinatorics},
abstract = {Decomposing an Eulerian graph into a minimum respectively maximum number of
edge disjoint cycles is an NP-complete problem. We prove that an Eulerian graph
decomposes into a unique number of cycles if and only if it does not contain
two edge disjoint cycles sharing three or more vertices. To this end, we
discuss the interplay of three binary graph operators leading to novel
constructive characterizations of two subclasses of Eulerian graphs. This
enables us to present a polynomial-time algorithm which decides whether the
number of cycles in a cycle decomposition of a given Eulerian graph is unique.
},
}