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

References

H.L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci. 209 (1-2) (1998), 1–45.

R. Diestel, Graph Theory, Graduate Texts in Mathematics, Springer, 2000.

H. Fleischner, Eulerian graphs and related topics, 1990.

I. Holyer. The NP-completeness of some edge-partition problems, SIAM J. Comput. 10 (4) (1981), 713–717.

J. Hopcroft and R. Tarjan, Algorithm 447: Efficient algorithms for graph manipulation, Com- mun. ACM 16 (6) (1973), 372–378.

M. Krivelevich, Z. Nutov, M.R. Salavatipour, J.V. Yuster, and R. Yuster, Approximation algorithms and hardness results for cycle packing problems, ACM Trans. Algorithms 3 (4) (2007).

S.O. Krumke and H. Noltemeier, Graphentheoretische Konzepte und Algorithmen (2009).

W. Mader. Konstruktion aller n-fach kantenzusammenhan ̈genden digraphen, European J. Combin. 3 (1) (1982), 63–67.

C. Otto and P. Recht, Maximum cycle packing using SPR-trees, Electron. J. Graph Theory Appl. 7 (1) (2019), 147–155.

B. Pe ́roche. NP-completeness of some problems of partitioning and covering in graphs, Discrete Appl. Math. 8 (2) (1984), 195–208.

W.T. Tutte, A theory of 3-connected graphs, Indag. Math. 23 (1961), 441–455. [12] D.B. West, Introduction to Graph Theory, 2001.


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