Directed cartesian-product graphs have unique factorizations that can be computed in polynomial time

AbstractThe cartesian product of directed, simple graphs D1 = (V1, A1) and D2 = (V2, A2) is a digraph D with V(D) = V1 × V2 and A(D) = {(ν1, ν2) → (w1, w2): ν1 = w1 and ν2 → w2 ϵA2 or ν2 = w2 and ν1 → w1ϵA1}. In this paper, we prove that directed graphs have unique prime factorizations under cartesian multiplication and that we can find the prime factorizations of weakly connected digraphs in polynomial time. This work extends recent work by Feigenbaum, Hershberger, Schäffer, and Winkler on cartesian factoring of undirected graphs