On The Sizes Of Least Common Multiples Of Several Pairs Of Graphs

Abstract

For nonempty graphs $G$ and $H$, $H$ is said to be $G$-decomposable (written $G|H$) if $E(H)$ can be partitioned into sets $E_1,\dots ,E_n$ such that the subgraph induced by each $E_i$ is isomorphic to $G$. If $H$ is a graph of minimum size such that $F|H$ and $G|H$, then $H$ is called a least common multiple of $F$ and $G$. The size of such a least common multiple is denoted by $\mathrm{l}\mathrm{c}\mathrm{m}(F,G)$. We show that if $F$ and $G$ are bipartite, then $\mathrm{l}\mathrm{c}\mathrm{m}(F,G)\le |V(F)|\cdot |V(G)|$, where equality holds if $(|V(F)|,|V(G)|)=1$. We also determine $\mathrm{l}\mathrm{c}\mathrm{m}(F,G)$ exactly if $F$ and $G$ are cycles or if $F=P_m,G=K_n$, where $n$ is odd and $(m-1,\frac{1}{2}(n-1))=1$, in the latter case extending a result in [{8}].