Maximum Cycle Packing in Eulerian Graphs Using Local Traces
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....