Thursday, 13:45 - 14:10 h, Room: H 3004


Eva-Maria Sprengel
An optimal cycle packing for generalized Petersen graphs P(n,k) with k even

Coauthor: Peter Recht


For an undirected graph G=(V,E) a maximum cycle packing is a collection of pairwise edge-disjoint cycles. The maximum cardinality of such a packing is denoted as the cycle packing number ν (G).
In general the determination of a maximum cycle packing and the cycle packing number, respectively, is NP-hard.
In this lecture we consider the family of generalized Petersen graphs P(n,k) with k even. We give a lower and an upper bound on the cycle packing number and outline the structure of one optimal cycle packing of such graphs.


Talk 2 of the contributed session Thu.2.H 3004
"Cycles in graphs" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra Online has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.