On m-factorizations of complete multigraphs and designs

2013-04-29
10:00-11:00
FAMNIT-SEMIN
Prof. György Kiss (Eötvös Loránd University, Hungary)
On m-factorizations of complete multigraphs and designs

The complete multigraph $\lambda K_{v}$ has $v$ vertices and $\lambda$ edges
joining each pair of vertices. An $m$-factor of the complete multigraph
$\lambda K_{v}$ is a set of pairwise vertex-disjoint $m$-regular subgraphs,
such that these subgraphs induce a partition of the vertices. An
$m$-factorization of $\lambda K_{v}$ is a set of pairwise edge-disjoint
$m$-factors such that these $m$-factors induce a partition of the edges. If
the $m$-factors are pairwise distinct, then it is called
\emph{simple}. Furthermore, an $m$-factorization of $\lambda K_{v}$ is
decomposable if there exist positive integers $\lambda_{1}$ and $\lambda_{2}$
such that $\lambda_{1}+\lambda_{2}=\lambda$ and $\lambda K_{v}$ is the union
of the $m$-factorizations $\lambda_{1}K_{v}$ and $\lambda_{2}K_{v}$, otherwise
it is called \emph{indecomposable}.

In this talk the existence of $m$-factorizations of $\lambda K_v$
for different values of $m$, $\lambda$ and $v$ is studied. Some new
infinite families of simple, indecomposable factorizations arising from
finite geometries will be presented.

The talk is based on a joint work with Christian Rubio-Montiel (UNAM, Mexico).