pith. sign in

arxiv: 1408.0371 · v1 · pith:EKGT26LPnew · submitted 2014-08-02 · 🧮 math.CO

A graph partition problem

classification 🧮 math.CO
keywords partitiongraphgraphscallemphgiveindexinteger
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.