COMMON MULTIPLES OF PATH, STAR AND CYCLE WITH COMPLETE BIPARTITE GRAPHS

Abstract

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