A Factoring Algorithm for Cartesian-Product Graphs

The cartesian product G=G sub 1 [] G sub 2 of simple, undirected graphs G sub 1 and G sub 2 is defined as follows. The vertex set V(G) is V(G sub 1) x V(G sub 2), and the edge set E(G) is {(x sub 1, y sub 1) - (x sub 2, y sub 2):(x sub 1=x sub 2 and y sub 1 - y sub element of E(G sub 1))}. More concretely, to form G sub 1 [] G sub 2, substitute a copy of G sub 2 for each vertex in G sub 1 and draw in edges between corresponding vertices of adjacent copies. (The symbol [] is used, because the cartesian product of two copies of K sub 2 is a four-cycle.)