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
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 $ {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?)

  • [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)

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

DOI: https://doi.org/10.1090/S0002-9947-1978-0545305-1
Keywords: Factorisations, complete graphs
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society