# Maximum Cycle Packing in Eulerian Graphs Using Local Traces

Peter Recht; Eva-Maria Sprengel

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 1, page 121-132
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topPeter Recht, and Eva-Maria Sprengel. "Maximum Cycle Packing in Eulerian Graphs Using Local Traces." Discussiones Mathematicae Graph Theory 35.1 (2015): 121-132. <http://eudml.org/doc/271227>.

@article{PeterRecht2015,

abstract = {For a graph G = (V,E) and a vertex v ∈ V , let T(v) be a local trace at v, i.e. T(v) is an Eulerian subgraph of G such that every walk W(v), with start vertex v can be extended to an Eulerian tour in T(v). We prove that every maximum edge-disjoint cycle packing Z* of G induces a maximum trace T(v) at v for every v ∈ V . Moreover, if G is Eulerian then sufficient conditions are given that guarantee that the sets of cycles inducing maximum local traces of G also induce a maximum cycle packing of G.},

author = {Peter Recht, Eva-Maria Sprengel},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {edge-disjoint cycle packing; local traces; extremal problems in graph theory},

language = {eng},

number = {1},

pages = {121-132},

title = {Maximum Cycle Packing in Eulerian Graphs Using Local Traces},

url = {http://eudml.org/doc/271227},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Peter Recht

AU - Eva-Maria Sprengel

TI - Maximum Cycle Packing in Eulerian Graphs Using Local Traces

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 1

SP - 121

EP - 132

AB - For a graph G = (V,E) and a vertex v ∈ V , let T(v) be a local trace at v, i.e. T(v) is an Eulerian subgraph of G such that every walk W(v), with start vertex v can be extended to an Eulerian tour in T(v). We prove that every maximum edge-disjoint cycle packing Z* of G induces a maximum trace T(v) at v for every v ∈ V . Moreover, if G is Eulerian then sufficient conditions are given that guarantee that the sets of cycles inducing maximum local traces of G also induce a maximum cycle packing of G.

LA - eng

KW - edge-disjoint cycle packing; local traces; extremal problems in graph theory

UR - http://eudml.org/doc/271227

ER -

## References

top- [1] S. Antonakopulos and L. Zhang, Approximation algorithms for grooming in optical network design, Theoret. Comput. Sci. 412 (2011) 3738-3751. doi:10.1016/j.tcs.2011.03.034[Crossref] Zbl1216.68044
- [2] F. Bäbler, Über eine spezielle Klasse Euler’scher Graphen, Comment. Math. Helv. 27 (1953) 81-100. doi:10.1007/BF02564555[Crossref] Zbl0050.17905
- [3] V. Bafna and P.A. Pevzner, Genome rearrangement and sorting by reversals, SIAM J. Comput. 25 (1996) 272-289. doi:10.1137/S0097539793250627[Crossref] Zbl0844.68123
- [4] A. Caprara, Sorting permutations by reversals and Eulerian cycle decompositions, SIAM J. Discrete Math. 12 (1999) 91-110. doi:10.1137/S089548019731994X[Crossref] Zbl0916.68074
- [5] A. Caprara, A. Panconesi and R. Rizzi, Packing cycles in undirected Graphs, J. Algorithms 48 (2003) 239-256. doi:10.1016/S0196-6774(03)00052-X[Crossref] Zbl1084.05067
- [6] G. Fertin, A. Labarre, I. Rusu, ´E. Tannier and S. Vialette, Combinatorics of Genome Rearrangement (MIT Press, Cambridge, Ma., 2009). Zbl1170.92022
- [7] J. Harant, D. Rautenbach, P. Recht and F. Regen, Packing edge-disjoint cycles in graphs and the cyclomatic number , Discrete Math. 310 (2010) 1456-1462. doi:10.1016/j.disc.2009.07.017[WoS][Crossref] Zbl1218.05076
- [8] J. Harant, D. Rautenbach, P. Recht, I. Schiermeyer and E.-M. Sprengel, Packing disjoint cycles over vertex cuts, Discrete Math. 310 (2010) 1974-1978. doi:10.1016/j.disc.2010.03.009[Crossref][WoS] Zbl1222.05121
- [9] J. Kececioglu and D. Sankoff, Exact and approximation algorithms for sorting by reversals with application to genome rearrangement , Algorithmica 13 (1997) 180-210. doi:10.1007/BF01188586[Crossref] Zbl0831.92014
- [10] M. Krivelevich, Z. Nutov, M.R. Salvatpour, J. Yuster and R. Yuster, Approximation algorithms and hardness results for cycle packing problems, ACM Trans. Algorithm 3(4)) (2007) Article 48. Zbl1297.05127
- [11] O. Ore, A problem regarding the tracing of graphs, Elem. Math. 6 (1951) 49-53. Zbl0043.38503
- [12] P. Recht and E.-M. Sprengel, Packing Euler graphs with traces, in: Operations Research Proceedings, Klatte, Lüthi and Schmedders (Ed(s)), (Heidelberg, New York, Dordrecht, London, Springer, 2011) 53-58. Zbl1306.05137

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.