ABSTRACT
We defined the direct product of graphs in Chapter 4 and deduced some of its elementary properties in Section 5.3. Now we explore the problem of prime factorization over this product. The chapter culminates with a proof that connected nonbipartite graphs in Γ0 factor uniquely into primes in Γ0. However, it is necessary to develop some preliminary ideas. We first define a relation R that is analogous to the relation S from Chapter 7. We then define a so-called Cartesian skeleton operation S : Γ0 → Γ that satisfies S(G ×H) = S(G)2S(H) for R-thin graphs. This allows us to exploit unique factorization over 2 to prove unique factorization of connected nonbipartite thin graphs over ×. Subsequently we extend this result to graphs that are not R-thin. Prime factorization leads naturally to a classification of the automorphisms of direct products.
