Graph cartesian products


On the basis that knowing some more about Graph Theory won’t do me any harm when thinking about operating system behaviour, I am reading about that too right now.

But I found the book’s explanation of a Graph Cartesian Product rather less than full, so here is my attempt to make it a bit clearer.

Say we have graph G_1 with vertices (v_1, v_2, v_3) and graph G_2 with vertices (w_1, w_2, w_3, w_4) , then our cartesian product graph is G_3 with vertices ((v_1, w_1), (v_1, w_2), (v1, w_3), (v_2, w_4),(v_2, w_1), (v_2, w_2), (v2, w_3), (v_2, w_4),(v_3, w_1), (v_3, w_2), (v3, w_3), (v_3, w_4))

Which vertices in this new graph are adjacent?

The vertices are adjacent if – and only if – taking the new vertices to be of the form (v_n, w_n) (v^{\prime}_n, w^{\prime}_n) – if v_n = v^{\prime}_n and w_n is adjacent to w^{\prime}_n in G_2 OR w_n = w^{\prime}_n and v_n is adjacent to v^{\prime}_n in G_1.