Laplacian spectrum for product graphs

Question

Let $G$ and $H$ be simple graphs.

I am interested in the Laplacian spectrum for various products of $G$ and $H$ namely the cartesian product, tensor product, lexicographical product and strong product as defined here https://en.wikipedia.org/wiki/Graph_product .

Given that $\lambda_1, \ldots, \lambda_n$ and $\mu_1, \ldots \mu_m$ are the eigenvalues of the Laplacians of $G$ and $H$ respectively, it is well known that the eigenvalues of the carteisan product of $G$ and $H$ are $$ \lambda_i + \mu_j \quad \hbox{for} \quad i = 1,\ldots,n \quad \hbox{and} \quad j = 1, \ldots,m.$$

I am interested in the relation between the eigenvalues of $G$ and $H$ with respect to the eigenvalues of the other mentioned products.

The same problem has already been considered for the spectrum of the adjacency matrix and solved under the general setting of the NEPS operation.

I suspect the same problem for the spectrum of the Laplacian eigenvalue to be slightly harder (as I think this would somehow have to characterize when is the lexicographical product of $G$ and $H$ connected) but I am not sure as I was not able to find any literature related to this matter.

Anyone happens to know the answer or could possibly provide some literature on this matter?

Answer 1

The Cartesian product is exceptional, there is no easy answer in general.

By way of example, consider the direct (aka tensor) product. Let $A_X$ denote the adjacency matrix of $X$ and let $D_X$ be the diagonal matrix of degrees. Then the Laplacian $L_X$ of $X$ is $D_X-A_X$. If $Z$ is the direct product of $X$ and $Y$ then $$ A_Z = A_X\otimes A_Y,\qquad D_Z =D_X\otimes D_Y $$ and thus $$ L_Z = D_X\otimes D_Y - A_X\otimes A_Y. $$ If $X$ and $Y$ are regular then $D_X\otimes D_Y$ is a scalar matrix and we can write down the eigenvalues of $L_Z$. But if they are not regular then the matrices $D_X\otimes D_Y$ and $A_X\otimes A_Y$ do not commute, and so you are looking for the eigenvalues of the difference of two symmetric matrices in terms of the eigenvalues of the "subtractands" (is that a word?) and this is a lost cause. (If you're looking at difference of symmetric matrices, you can always reduce to the case where one is diagonal.)

For the lexicographic product, you can only write down the spectrum of $A_Z$ in terms of the factors if the base graph is regular. The obvious variant of the analysis for the direct product will give the eigenvalues of $L_Z$ if both graphs are regular (because then the matrices in the expression for $L_Z$ all commute).

And if you're forced to restrict yourself to regular graphs, you might as well just use the usual adjacency matrix.

Answer 2

In addition to the good questions already given, let me add a reference to R. Hammack, W. Imrich, and S. Klavžar, Handbook of Product Graphs, CRC 2011. I do not have the book at hand, but if I remember correctly the authors do suggest that each kind of product is essentially compatible with one, and just one, of the classical graph matrices (Laplacian, adjacency, normalised Laplacian are those they consider, if I'm not mistaken).

Answer 3

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 eigensolution of Laplacian matrices of product graphs. In this way exact or approximate methods could be introduced. A paper includes aforementioned concepts is in press at Acta Mechanica with the title "Laplacian Matrices of Product Graphs: Applications in Structural Mechanics"

Link