Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-23T19:12:08.453Z Has data issue: false hasContentIssue false
  • English
  • Français

Isomorphic factorisations V: Directed graphs

Part of: Graph theory

Published online by Cambridge University Press:  26 February 2010

Frank Harary ,
Robert W. Robinson  and
Nicholas C. Wormald
Frank Harary
Affiliation:
Department of Mathematics, University of Michigan, Ann Arbor, Michigan, 48109, U.S.A.
Robert W. Robinson
Affiliation:
Department of Mathematics, University of Newcastle, New South Wales, 2308, Australia.
Nicholas C. Wormald
Affiliation:
Department of Mathematics, University of Newcastle, New South Wales, 2308, Australia.
Get access

Abstract

An isomorphic factorisation of a digraph D is a partition of its arcs into mutually isomorphic subgraphs. If such a factorisation of D into exactly t parts exists, then t must divide the number of arcs in D. This is called the divisibility condition. It is shown conversely that the divisibility condition ensures the existence of an isomorphic factorisation into t parts in the case of any complete digraph. The sufficiency of the divisibility condition is also investigated for complete m-partite digraphs. It is shown to suffice when m = 2 and t is odd, but counterexamples are provided when m = 2 and t is even, and when m = 3 and either t = 2 or t is odd.

MSC classification

Secondary: 05C20: Directed graphs (digraphs), tournaments
Type
Research Article
Information
Mathematika , Volume 25 , Issue 2 , December 1978 , pp. 279 - 285
Copyright
Copyright © University College London 1978

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Bermond, J. C. and Sotteau, D.. “Graph decompositions and G-designs”, Proc. 5th British Combinatorial Conf., Nash-Williams, C. and Sheehan, J., eds. (Utilitas, Winnipeg, 1976), 53–72.Google Scholar
2.Harary, F.. Graph Theory (Addison-Wesley, Reading, Mass., 1969).CrossRefGoogle Scholar
3.Harary, F., Heinrich, K. and Wallis, W. D.. “Decomposition of complete symmetric digraphs into the four oriented quadrilaterals”, Proc. Int. Conf. Combinatorial Theory, Holton, D. and Seberry, J., eds. Springer Notes, 686 (1978), 165–173.Google Scholar
4.Harary, F., Robinson, R. W. and Wormald, N. C.. “Isomorphic factorisations I: Complete graphs”, Trans. Amer. Math. Soc., 242 (1978), 243–260.Google Scholar
5.Harary, F., Robinson, R. W. and Wormald, N. C.. “Isomorphic factorisations III: Complete multipartite graphs”, Proc. Int. Conf. Combinatorial Theory Holton, D. and Seberry, J., eds. Springer Notes, 686 (1978), 47–54.Google Scholar
6.Harary, F. and Wallis, W. D.. “Isomorphic Factorisations II: Combinatorial designs”, Proc. 8th Southeastern Conf. on Combinatorics, Graph Theory and Computing (Utilitas, Winnipeg, 1978), 13–28.Google Scholar
7.Köhler, E.. “Zerlegung total gerichteter Graphen in Kreise”, Manuscripta Math., 19(1976), 151–164.CrossRefGoogle Scholar
8.Moon, J. W.. Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968).Google Scholar
9.Wilson, R. M.. “Decompositions of complete graphs into subgraphs isomorphic to a given graph”, Proc. 5th British Combinatorial Conf., Nash-Williams, C. and Sheehan, J., eds. (Utilitas, Winnipeg, 1976), 647–659.Google Scholar