Isomorphic Factorisations V: Directed graphs

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

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)279-285
Number of pages7
Issue number2
Publication statusPublished - 1978
Externally publishedYes

Cite this