On the sizes of least common multiples of stars versus cycles

Abstract

If G and H are nonempty graphs, then H is said to be G-decomposable if E(H) can be partitioned into sets E₁,E₂, . . . , E_n such that the subgraph induced by each E_i, i = 1, 2, . . . , n, is isomorphic to G. If H has no isolated vertices and is a graph of minimum size which is both G₁-dcomposable and G₂-decomposable, where G₁ and G₂ are nonempty graphs, then H is called a least common multiple of G₁ and G₂. The size of a least common multiple of G₁ and G₂ is denoted by lcm(G₁,G₂). Some special cases of a conjecture about lcm(C_2n+1, K_l,1) by G. Chartrand et al. are proved. We also give a counterexample to show when it is false and give some comments and an improved conjecture.