A graph partition problem

Sebastian M. Cioabă, Peter Jephson Cameron

Research output: Contribution to journalArticlepeer-review

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 mKn into copies of G? We show that there is an integer m0, which we call the 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 m0. Trivial divisibility conditions derived from G give an integer m1 that divides m0; we call the quotient m0/m1 the 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.
Original languageEnglish
Pages (from-to)972-983
Number of pages12
JournalThe American Mathematical Monthly
Volume122
Issue number10
DOIs
Publication statusPublished - Dec 2015

Keywords

  • graph, design, affine plane

Fingerprint

Dive into the research topics of 'A graph partition problem'. Together they form a unique fingerprint.

Cite this