Principal common divisors of graphs

A graph H divides a graph G, written H | G, if G is H-decomposable. If H ≠ G, then H properly divides G. A graph G is a principal common divisor if there exist graphs G1 and G2 such that G properly divides G1 and G2, and if H is any graph such that H | G1 and H | G2, then H | G. Several graphs that are principal common divisors are described. It is shown that complete graphs are not principal common divisors. © 1993 Academic Press, Inc.