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

DOI:
https://doi.org/10.1090/S0002-9947-1978-0545305-1

MathSciNet review:
0545305

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An isomorphic factorisation of the complete graph is a partition of the lines of into *t* isomorphic spanning subgraphs *G*; we then write , and . If the set of graphs is not empty, then of course . Our principal purpose is to prove the converse. It was found by Laura Guidotti that the converse does hold whenever or . We give a new and shorter proof of her result which involves permuting the points and lines of . The construction developed in our proof happens to give all the graphs in and . The Divisibility Theorem asserts that there is a factorisation of into *t* isomorphic parts whenever *t* divides . 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 .

**[1]**J.-C. Bermond and D. Sotteau,*Graph decompositions and 𝐺-designs*, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) Utilitas Math., Winnipeg, Man., 1976, pp. 53–72. Congressus Numerantium, No. XV. MR**0450102****[2]**Laura Guidotti,*Sulla divisibilità dei grafi completi*, Riv. Mat. Univ. Parma (3)**1**(1972), 231–237 (Italian). MR**0382074****[3]**Frank Harary,*Graph theory*, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR**0256911****[4]**Frank Harary and Edgar M. Palmer,*Graphical enumeration*, Academic Press, New York-London, 1973. MR**0357214****[5]**Pavol Hell, Anton Kotzig, and Alexander Rosa,*Some results on the Oberwolfach problem (decomposition of complete graphs into isomorphic quadratic factors)*, Aequationes Math.**12**(1975), 1–5. MR**0379291**, https://doi.org/10.1007/BF01834032**[6]**Pauline Cain Hogarth,*Decomposition of complete graphs into 6-stars and into 10-stars*, Combinatorial mathematics, III (Proc. Third Australian Conf., Univ. Queensland, St. Lucia, 1974) Springer, Berlin, 1975, pp. 136–142. Lecture Notes in Math., Vol. 452. MR**0379292****[7]**Anton Kotzig,*On certain vertex-valuations of finite graphs*, Utilitas Math.**4**(1973), 261–290. MR**0384616****[8]**Anton Kotzig and Alexander Rosa,*Decomposition of complete graphs into isomorphic factors with a given diameter*, Bull. London Math. Soc.**7**(1975), 51–57. MR**0369175**, https://doi.org/10.1112/blms/7.1.51**[9]**D. K. Ray-Chaudhuri and Richard M. Wilson,*Solution of Kirkman’s schoolgirl problem*, Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968) Amer. Math. Soc., Providence, R.I., 1971, pp. 187–203. MR**0314644****[10]**R. C. Read,*On the number of self-complementary graphs and digraphs*, J. London Math. Soc.**38**(1963), 99–104. MR**0146819**, https://doi.org/10.1112/jlms/s1-38.1.99**[11]**Gerhard Ringel,*Selbstkomplementäre Graphen*, Arch. Math. (Basel)**14**(1963), 354–358 (German). MR**0154273**, https://doi.org/10.1007/BF01234967**[12]**-,*Problem*25, Theory of Graphs and Its Applications, (M. Fiedler, ed.), Academic Press, New York, 1964, p. 162.**[13]**Alexander Rosa and Charlotte Huang,*Another class of balanced graph designs: balanced circuit designs*, Discrete Math.**12**(1975), 269–293. MR**0419269**, https://doi.org/10.1016/0012-365X(75)90051-5**[14]**Herbert John Ryser,*Combinatorial mathematics*, The Carus Mathematical Monographs, No. 14, Published by The Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York, 1963. MR**0150048****[15]**Horst Sachs,*Über selbstkomplementäre Graphen*, Publ. Math. Debrecen**9**(1962), 270–288 (German). MR**0151953****[16]**G. J. Simmons and J. A. Davis,*Pair designs*, Comm. Statist.**4**(1975), 255–272. MR**0428632****[17]**Richard M. Wilson,*Decompositions of complete graphs into subgraphs isomorphic to a given graph*, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976, pp. 647–659. MR**0396347****[18]**Sumiyasu Yamamoto, Hideto Ikeda, Shinsei Shige-eda, Kazuhiko Ushio, and Noboru Hamada,*On claw-decomposition of complete graphs and complete bigraphs*, Hiroshima Math. J.**5**(1975), 33–42. MR**0379300**

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

DOI:
https://doi.org/10.1090/S0002-9947-1978-0545305-1

Keywords:
Factorisations,
complete graphs

Article copyright:
© Copyright 1978
American Mathematical Society