On graphs that have a unique least common multiple

Abstract

A graph $G$ without isolated vertices is a least common multiple of two graphs $H_1$ and $H_2$ if $G$ is a smallest graph, in terms of number of edges, such that there exists a decomposition of $G$ into edge disjoint copies of $H_1$ and there exists a decomposition of $G$ into edge disjoint copies of $H_2$. The concept was introduced by G. Chartrand et al. and they proved that every two nonempty graphs have a least common multiple. Least common multiple of two graphs need not be unique. In fact two graphs can have an arbitrary large number of least common multiples. In this paper graphs that have a unique least common multiple with $P_3 \cup K_2$ are characterized.

Keywords

• graph decomposition
• common multiple of graphs