Least Common Multiple of a Cycle and a Star

A graph G is decomposable into the subgraphs G1, G2,…, Gn of G if no Gi, (i = 1, 2,…, n) has isolated vertices and the edge set E(G) can be partitioned into the subsets E(G1),E(G2),…, E(Gn). If Gi ≈ H for every i, we say that G is H-decomposable and we write H∣G. A graph F without isolated vertices is a least common multiple of the graphs G1 and G2, if F is a graph of minimum size such that F is both G1-decomposable and G2-decomposable. The size (the number of edges) of a least common multiple of two graphs G1 and G2 is denoted by lcm (G1,G2). G. Chartrand et al [1], found lcm (C2k,K1,i) and lcm (C3,K1,l). For general odd integer n, they introduced a conjecture. Ping Wang [4] proved the conjecture true when n = 5. In this paper, we show that the conjecture is true for the case when l is an odd integer and (n,l) = 1. When 1 < d < l and n/d · d+1/2 ≥ 2l/d + 1, where d = gcd(n, l), we introduce a new formula and prove it.