Cycle decompositions of graphs

Event details

When

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

Where

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

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