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.