Back to Search
Start Over
A graph partition problem
- 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.
- Subjects :
- Mathematics - Combinatorics
05C99, 05B25
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1408.0371
- Document Type :
- Working Paper