Cycle decompositions and constructive characterizations

Irene Heinrich, Manuel Streicher

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.


Keywords


constructive characterization, cycle decomposition, cycle packing, cycle covering, Eulerian graphs

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2019.7.2.15

Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats