Minimum Cycle Decomposition: A Constructive Characterization for Graphs of Treewidth Two with Node Degrees Two and Four

2017/01/19 by Irene Heinrich, Heinrich, Irene, Sven O. Krumke +1
Computer Science · Engineering · #Advanced Graph Theory Research #Interconnection Networks and Systems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1701.05516

Abstract

Substantial efforts have been made to compute or estimate the minimum number c(G) of cycles needed to partition the edges of an Eulerian graph. We give an equivalent characterization of Eulerian graphs of treewidth 2 and with maximum degree 4. This characterization enables us to present a linear time algorithm for the computation of c(G) for all G in this class.

Related

• Cycle Decompositions and Constructive Characterizations
• Cycle decompositions of pathwidth-6 graphs
• Minimum degree conditions for monochromatic cycle partitioning
• Hajós' cycle conjecture for small graphs
• Partitioning a graph into a cycle and a sparse graph