No label defined (Q4940050)

The authors deal with the so-called least common multiple of graphs (together with the greatest common divisor of graphs; the study of the subject started approximately in 1993). The following definitions are needed: a graph \(G\) is \(H\)-decomposable if \(G\) can be decomposed into graphs isomorphic to \(H\). A graph \(G\) without isolated vertices is a least common multiple of two graphs \(G_1\) and \(G_2\) if \(G\) is a graph of minimum size such that \(G\) is both \(G_1\)-decomposable and \(G_2\)-decomposable. A graph \(G\) without isolated vertices is a greatest common divisor of \(G_1\) and \(G_2\) if \(G\) is a graph of maximum size such that both \(G_1\) and \(G_2\) are \(G\)-decomposable. It is clear that every two graphs have a greatest common divisor and it was also shown that every two graphs have a least common multiple. In the present paper the authors concentrate on the problem of how many greatest common divisors and least common multiples a pair of graphs can have. They show, e.g., that for every positive integer \(n\), there are graphs \(G_1\) and \(G_2\) having exactly \(n\) greatest common divisors (least common multiples). Examples of further results are: (i) the characterization of all graphs \(G\) for which \(G\) and \(P_3\) (the path on 3 vertices) have a unique least common multiple, and (ii) the demonstration that the stars \(K_{1,r}\) and \(K_{1,s}\) have a unique least common multiple if and only if \(r\) and \(s\) are not relatively prime. The proofs of the paper rely on the construction (straightforward) of the needed graphs and the use of statements on arithmetics and divisibility of integers.