Common multiples of paths and stars with complete graphs

Abstract

A graph G is a common multiple of two graphs H₁ and H₂ if there exists a decomposition of G into edge-disjoint copies of H₁ and also a decomposition of G into edge-disjoint copies of H₂. If G is a common multiple of H₁ and H₂ and G has q edges, then we call G a (q, H₁, H₂) graph. Our paper deals with the following question: ''Given two graphs H₁ and H₂, for which values of q does there exist a (q, H₁, H₂) graph?'' when H₁ is either a path or a star with 3 or 4 edges and H₂ is a complete graph.