Greatest common divisors and least common multiples of graphs

A graphH divides a graphG, writtenH|G, ifG isH-decomposable. A graphG without isolated vertices is a greatest common divisor of two graphsG₁ andG₂ ifG is a graph of maximum size for whichG|G₁ andG|G₂, while a graphH without isolated vertices is a least common multiple ofG₁ andG₂ ifH is a graph of minimum size for whichG₁|H andG₂|H. It is shown that every two nonempty graphs have a greatest common divisor and least common multiple. It is also shown that the ratio of the product of the sizes of a greatest common divisor and least common multiple ofG₁ andG₂ to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG₁,G₂ of graphs are determined, including when one ofG₁ andG₂ is a cycle of even length and the other is a star.G. C's research was supported in part by the Office of Naval Research, under Grant N00014-91-I-1060