Cycle Decompositions and Constructive Characterizations

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 en...

Full description

Saved in:
Bibliographic details
Main Author: Heinrich, Irene
Streicher, Manuel
Format: Journal Article
Language: English
Place of publication: 30.08.2017
Data of publication: 2017-08-30
Online Access: Fulltext
Database: arXiv Mathematics
Database information Databases - DBIS