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

Print ISSN: 0972-7752 | Online ISSN: 2582-0850 | Total Downloads : 26

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.

.....

Download PDF 26 Click here to Subscribe now