Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Isomorphic factorisations. I. Complete graphs

Authors: Frank Harary, Robert W. Robinson and Nicholas C. Wormald
Journal: Trans. Amer. Math. Soc. 242 (1978), 243-260
MSC: Primary 05-02; Secondary 05C99
MathSciNet review: 0545305
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An isomorphic factorisation of the complete graph $ {K_p}$ is a partition of the lines of $ {K_p}$ into t isomorphic spanning subgraphs G; we then write $ G\vert{K_p}$, and $ G \in {K_p}/t$. If the set of graphs $ {K_p}/t$ is not empty, then of course $ t\vert 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 $ {K_p}$. The construction developed in our proof happens to give all the graphs in $ {K_6}/3$ and $ {K_7}/3$. The Divisibility Theorem asserts that there is a factorisation of $ {K_p}$ 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$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05-02, 05C99

Retrieve articles in all journals with MSC: 05-02, 05C99

Additional Information

Keywords: Factorisations, complete graphs
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society