The Laplacian spectrum of hierarchical product graphs and unique prime factorization

It is known that each connected graph X can be represented as the hierarchical product G ⊓ H [ h ] of a unique prime graph G and a unique rooted graph H [ h ] . Here, we derive this result from the properties of the eigensystem of the Laplacian matrix of X . This implies the existence of a unique standard prime factorization of connected graphs with respect to the hierarchical product, although other (non-standard) prime factorizations may exist. We prove that rebracketing and the choice of appropriate roots will transform any prime factorization into the unique standard form. For connected graphs, this implies that the prime factors of any prime factorization are isomorphic as unrooted graphs to those in the standard form.