Back to Search Start Over

A graph partition problem

Authors :
Cameron, Peter J.
Cioabă, Sebastian M.
Publication Year :
2014

Abstract

Given a graph $G$ on $n$ vertices, for which $m$ is it possible to partition the edge set of the $m$-fold complete graph $mK_n$ into copies of $G$? We show that there is an integer $m_0$, which we call the \emph{partition modulus of $G$}, such that the set $M(G)$ of values of $m$ for which such a partition exists consists of all but finitely many multiples of $m_0$. Trivial divisibility conditions derived from $G$ give an integer $m_1$ which divides $m_0$; we call the quotient $m_0/m_1$ the \emph{partition index of $G$}. It seems that most graphs $G$ have partition index equal to $1$, but we give two infinite families of graphs for which this is not true. We also compute $M(G)$ for various graphs, and outline some connections between our problem and the existence of designs of various types.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1408.0371
Document Type :
Working Paper