Isomorphic factorisations. I: Complete graphs

Frank Harary, Robert W. Robinson, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

46 Citations (Scopus)


An isomorphic factorisation of the complete graph Kp is a partition of the lines of Kp into t isomorphic spanning subgraphs G; we then write GKp and G e Kp/t. If the set of graphs Kp/t is not empty, then of course t\p(p - 1)/2. Our principal purpose is to prove the converse. It was found by Laura Guidotti that the converse does hold whenever (t, p) = 1 or (t, p - 1) = 1 We give a new and shorter proof of her result which involves permuting the points and lines of Kp. The construction developed in our proof happens to give all the graphs in K6/3 and K7/3. The Divisibility Theorem asserts that there is a factorisation of Kp into t isomorphic parts whenever t divides p(p - 1)/2. The proof to be given is based on our proof of Guidotti's Theorem, with embellishments to handle the additional difficulties presented by the cases when t is not relatively prime to p or p - 1.

Original languageEnglish
Pages (from-to)243-260
Number of pages18
JournalTransactions of the American Mathematical Society
Publication statusPublished - 1978
Externally publishedYes


  • Complete graphs
  • Factorisations

Cite this