Skip to content. | Skip to navigation

Personal tools

This is SunRain Plone Theme


You are here: Home / Discrete Mathematics Seminars / Cycle decompositions of graphs

Cycle decompositions of graphs

Event details


Mar 14, 2019
from 03:00 PM to 04:30 PM


Seminar Room/Section of Mathematics/Department of Civil, Enviromental, Architectural Engineering and Mathematics/University of Brescia

Contact Name

Add event to calendar

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