Spectral methods for matrix product factorization

A graph G is factored into graphs H and K via a matrix product if there exist adjacency matrices A , B , and C of G , H , and K , respectively, such that A = B C . In this paper, we study the spectral aspects of the matrix product of graphs, including regularity, bipartiteness, and connectivity. We show that if a graph G is factored into a connected graph H and a graph K with no isolated vertices, then certain properties hold. If H is non-bipartite, then G is connected. If H is bipartite and G is not connected, then K is a regular bipartite graph, and consequently, n is even. Furthermore, we show that trees are not factorizable, which answers a question posed by Maghsoudi et al.