2026/07/08 by Clemens Brand, Wilfried Imrich
Mathematics · #Rings, Modules, and Algebras #Graph theory and applications #Finite Group Theory Research
paper · doi:10.1016/j.disc.2026.115318
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.