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

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, \ldots, 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{lcm}(F,G)\). We show that if \(F\) and \(G\) are bipartite, then \(\mathrm{lcm}(F,G) \leq |V(F)|\cdot|V(G)|\), where equality holds if \((|V(F)|,|V(G)|) = 1\). We also determine \(\mathrm{lcm}(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}].