# Laplacian spectrum for product graphs

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?

• For the tensor product it's $\lambda_i \cdot \mu_j$ (special case of the spectrum of the tensor product of any two linear operators). Aug 10, 2011 at 19:34
• Wouldn't that imply that the tensor product is always disconencted, since the multiplicty of the eigenvalue 0 in the Laplacian of $G$, counts the number of connected components in $G$? Aug 10, 2011 at 20:41
• See sections 1.4.6, 1.4.7 and 1.4.8 of homepages.cwi.nl/~aeb/math/ipm1.pdf Aug 10, 2011 at 21:04
• I believe this pdf refers to the spectrum of the adjacency matrix and not the Laplacian. Otherwise I do not see how the eigenvalues of the tensor products are $\lambda_i \cdot \mu_j$ since this would immediately imply the tensor product is never connected - a contradiction. Aug 10, 2011 at 21:30
• Sorry, I indeed meant the adjacency matrix. If the graphs have constant degree then this also yields the spectrum of the graph Laplacian, but in general it's a different question. Aug 10, 2011 at 22:15

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.

• I also suspected it to be kind of hard, but it seems that someone was able to find an answer. In the talks presetend at WCLAM 08 pims.math.ca/files/program_0.pdf there is a talk named On graph products and the resulting spectra . However, there is no article to be found online in which the author covers the topic presented in this talk. Aug 11, 2011 at 8:54
• You cannot read much from the title of a talk - they may have just treated special cases, for example. Aug 11, 2011 at 11:39
• Sure! I have contacted the author and he said he was able to give a complete characterization of the Laplacian spectrum for product graphs. He said it was communicated to some journals and it will (hopefully) be avaiable soon. Aug 11, 2011 at 15:16

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).

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"