Isomorphic factorisations. I. Complete graphs

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

doi:10.1090/S0002-9947-1978-0545305-1

Isomorphic factorisations. I. Complete graphs
HTML articles powered by AMS MathViewer

by Frank Harary, Robert W. Robinson and Nicholas C. Wormald PDF

Trans. Amer. Math. Soc. 242 (1978), 243-260 Request permission

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|{K_p}$, and $G \in {K_p}/t$. If the set of graphs ${K_p}/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 ${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

J.-C. Bermond and D. Sotteau, Graph decompositions and $G$-designs, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976, pp. 53–72. MR 0450102
Laura Guidotti, Sulla divisibilità dei grafi completi, Riv. Mat. Univ. Parma (3) 1 (1972), 231–237 (Italian). MR 382074
Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911, DOI 10.21236/AD0705364
Frank Harary and Edgar M. Palmer, Graphical enumeration, Academic Press, New York-London, 1973. MR 0357214
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 379291, DOI 10.1007/BF01834032
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) Lecture Notes in Math., Vol. 452, Springer, Berlin, 1975, pp. 136–142. MR 0379292
Anton Kotzig, On certain vertex-valuations of finite graphs, Utilitas Math. 4 (1973), 261–290. MR 384616
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 369175, DOI 10.1112/blms/7.1.51
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
R. C. Read, On the number of self-complementary graphs and digraphs, J. London Math. Soc. 38 (1963), 99–104. MR 146819, DOI 10.1112/jlms/s1-38.1.99
Gerhard Ringel, Selbstkomplementäre Graphen, Arch. Math. (Basel) 14 (1963), 354–358 (German). MR 154273, DOI 10.1007/BF01234967

Problem

Alexander Rosa and Charlotte Huang, Another class of balanced graph designs: balanced circuit designs, Discrete Math. 12 (1975), 269–293. MR 419269, DOI 10.1016/0012-365X(75)90051-5
Herbert John Ryser, Combinatorial mathematics, The Carus Mathematical Monographs, No. 14, Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York, 1963. MR 0150048, DOI 10.5948/UPO9781614440147
Horst Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962), 270–288 (German). MR 151953
G. J. Simmons and J. A. Davis, Pair designs, Comm. Statist. 4 (1975), 255–272. MR 428632, DOI 10.1080/03610917508548353
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
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 379300