Authors:K. S. Bagga, L. W. Beineke, G. Chartrand, and O. R. Oellermann
For an (r − 2)-edge-connected graphG (r ≥ 3) for orderp containing at mostk edge cut sets of cardinalityr − 2 and for an integerl with 0 ≤l ≤ ⌊p/2⌋, it is shown that (1) ifp is even, 0 ≤k ≤ r(l + 1) − 1, and
Authors:G. Chartrand, L. Holley, G. Kubicki, and M. Schultz
A graphH divides a graphG, writtenH|G, ifG isH-decomposable. A graphG without isolated vertices is a greatest common divisor of two graphsG1 andG2 ifG is a graph of maximum size for whichG|G1 andG|G2, while a graphH without isolated vertices is a least common multiple ofG1 andG2 ifH is a graph of minimum size for whichG1|H andG2|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 ofG1 andG2 to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG1,G2 of graphs are determined, including when one ofG1 andG2 is a cycle of even length and the other is a star.