In relation with Laplacian matrices of Graph Products one could consider a Theorem for formation of that matrix. this theorem will help us to argue about eigensoultion of Laplacian matrices of product graphs. In this way exact or approximate methods could be introduced. 
A paper includes aformentioned concepts is in press at *Acta Mechanica* with the title *"Laplacian Matrices of Product Graphs: Applications in Structural Mechanics"*

http://www.springerlink.com/content/44287522r1733051