Premium
Isomorphic factorisations V: Directed graphs
Author(s) -
Harary Frank,
Robinson Robert W.,
Wormald Nicholas C.
Publication year - 1978
Publication title -
mathematika
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.955
H-Index - 29
eISSN - 2041-7942
pISSN - 0025-5793
DOI - 10.1112/s0025579300009529
Subject(s) - mathematics , divisibility rule , digraph , combinatorics , factorization , counterexample , partition (number theory) , discrete mathematics , graph , algorithm
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.