Hierarchical product graphs and their prime factorization

The hierarchical and the generalized hierarchical product of graphs, together with their multiary and rooted versions, are variants of the Cartesian product. They are not commutative, and only the rooted versions are associative. We prove that finite connected graphs have unique prime factorizations with respect to the rooted hierarchical product, the multiary hierarchical product, and the rooted generalized hierarchical product. For the generalized hierarchical product, we disprove a claim about unique prime factorization by Anderson, Guo, Tenney, and Wash from 2017. We also describe the interrelation between the automorphism groups of connected graphs with the groups of their prime factors in the cases of unique prime factorization, and in the case of the standard prime factorization with respect to the hierarchical product. For finite trees, we show that their prime factors can be computed in subquadratic time.