Products and Factorizations of Graphs

Abstract

It is shown that the cardinal product of graphs does not satisfy unique prime factorization even for a very restrictive class of graphs. It is also proved that every connected graph has a decomposition as a weak cartesian product into indecomposable factors and that this decomposition is unique to within isomorphisms. This latter result is established by considering a certain class of equivalence relations on the edge set of a graph and proving that this collection is a principal filter in the lattice of all equivalences. The least element of this filter is then used to decompose the graph into a weak cartesian product of prime graphs that is unique to within isomorphisms.