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.

Keywords and Phrases

Graph Decomposition, Common Multiples of Graphs, Path, Star, Cycle, Complete Bipartite Graph.

A.M.S. subject classification

05C38, 05C51, 05C70.

.....