# Cycle decompositions of graphs

## Event details

### When

from 03:00 PM to 04:30 PM

### Where

### Contact Name

**Dr. Francesca Merola, University of Roma Tre**

A cycle decomposition for a graph \(\Gamma\) is a set \(\cal B\) of cycles of \(\Gamma\) whose edges partition the edge set of \(\Gamma\); if the cycles in \(\cal B\) all have the same length \(\ell\), we speak of an \(\ell\)-cycle system of \(\Gamma\). An \(\ell\)-cycle system is regular if there is an automorphism group \(G\) of the graph \(\Gamma\) acting sharply transitively on the vertices of \(\Gamma\) and permuting the cycles of \(\cal B\), and it is called cyclic if \(G\) is the cyclic group.

If \(\Gamma\) is the complete graph on \(v\) vertices, or the so called cocktail party graph \(K_{2v} − F\) (\(F\) a \(1\)-factor of \(K_{2v}\)), the problem of determining for which values of \(\ell\) and \(v\) there exists an \(\ell\)-cycle system has been completely solved; the analogous existence problem for cyclic cycle systems is still open, although we have many results towards that end.

When \(\Gamma\) is \(K_m[n]\), the complete multipartite graph with \(m\) parts each of size \(n\), only partial results on the existence of \(\ell\)-cycle systems are known, and little is known on regular cycle systems.

In the talk I would like to survey some of the known results and techniques for cycle decompositions. I would also like to discuss some new results, obtained jointly with Andrea Burgess and Tommaso Traetta, regarding the existence of cyclic cycle systems for the complete multipartite graph \(K_m[n]\).

Document Actions