On least common multiples of digraphs

Abstract

For a digraph H without isolated vertices, a digraph D is H-decomposable if D can be decomposed into subdigraphs each of which is isomorphic to H. A digraph H is a least common multiple of D₁ and D₂ if H is a digraph of minimum size that is both D₁-decomposable and D₂-decomposable. Least common multiples of two directed stars are shown to exist and their sizes are determined in several instances. Least common multiples of every two multidigraphs are shown to exist.