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 Free Access

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 G-designs*, Proceedings of the Fifth British Combinatorial Conference, (C. St. J. A. Nash-Williams and J. Sheehan, eds.), Utilities Math., Winnipeg, 1976, pp. 53-72. MR**0450102 (56:8401)****[2]**L. Guidotti,*Sulla divisibilità dei grafi completi*, Riv. Mat. Univ. Parma**1**(1972), 231-237. MR**0382074 (52:2962)****[3]**F. Harary,*Graph theory*, Addison-Wesley, Reading, Mass., 1969. MR**0256911 (41:1566)****[4]**F. Harary and E. M. Palmer,*Graphical enumeration*, Academic Press, New York, 1973. MR**0357214 (50:9682)****[5]**P. Hell, A. Kotzig and A. Rosa,*Some results on the Oberwolf ach problem: Decomposition of complete graphs into isomorphic quadratic factors*, Aequationes Math.**12**(1975), 1-5. MR**0379291 (52:197)****[6]**P. C. Hogarth,*Decomposition of complete graphs into*6-*stars and into*10-*stars*, Combinatorial Mathematics III, Springer-Verlag, Berlin, 1975, pp. 136-142. MR**0379292 (52:198)****[7]**A. Kotzig,*On certain vertex valuations of finite graphs*, Utilitas Math.**4**(1973), 261-290. MR**0384616 (52:5490)****[8]**A. Kotzig and A. Rosa,*Decomposition of complete graphs into isomorphic subgraphs with a given diameter*, Bull. London Math. Soc.**7**(1975), 51-57. MR**0369175 (51:5410)****[9]**D. K. Ray-Chaudhuri and R. M. Wilson,*Solution of Kirkman's schoolgirl problem*, Proc. Sympos. Pure Math., vol. 19, Combinatorics, Amer. Math. Soc., Providence, R. I., 1971, pp. 187-203. MR**0314644 (47:3195)****[10]**R. C. Read,*On the number of self-complementary graphs and digraphs*, J. London Math. Soc.**38**(1963), 99-104. MR**0146819 (26:4339)****[11]**G. Ringel,*Selbstkomplementäre Graphen*, Arch. Math.**14**(1963), 354-358. MR**0154273 (27:4222)****[12]**-,*Problem*25, Theory of Graphs and Its Applications, (M. Fiedler, ed.), Academic Press, New York, 1964, p. 162.**[13]**A. Rosa and C. Huang,*Another class of balanced block designs*:*balanced circuit designs*, Discrete Math.**12**(1975), 269-293. MR**0419269 (54:7292)****[14]**H. J. Ryser,*Combinatorial mathematics*, Carus Monograph 14, Math. Assoc. Amer., 1963. MR**0150048 (27:51)****[15]**H. Sachs,*Über selbstkomplementäre Graphen*, Publ. Math. Debrecen**9**(1962), 270-288. MR**0151953 (27:1934)****[16]**G. J. Simmons and J. A. Davis,*Pair designs*, Comm. Statist.**4**(1975), 255-272. MR**0428632 (55:1653)****[17]**R. M. Wilson,*Decomposition of complete graphs into subgraphs isomorphic to a given graph*, Proceedings of the Fifth British Combinatorial Conference, (C. St. J. A. Nash-Williams and J. Sheehan, eds.) Utilitas Math., Winnipeg, 1976, pp. 647-659. MR**0396347 (53:214)****[18]**S. Yamamoto, H. Ikeda, S. Shige-eda, K. Ushio and N. Hamada,*On claw-decomposition of complete graphs and complete bigraphs*, Hiroshima Math. J.**5**(1975), 33-42. MR**0379300 (52:205)**

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