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 http://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?

  • 2
    $\begingroup$ 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). $\endgroup$ – Noam D. Elkies Aug 10 '11 at 19:34
  • $\begingroup$ 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$? $\endgroup$ – Jernej Aug 10 '11 at 20:41
  • $\begingroup$ See sections 1.4.6, 1.4.7 and 1.4.8 of homepages.cwi.nl/~aeb/math/ipm1.pdf $\endgroup$ – Alain Valette Aug 10 '11 at 21:04
  • $\begingroup$ 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. $\endgroup$ – Jernej Aug 10 '11 at 21:30
  • $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Aug 10 '11 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.

  • $\begingroup$ 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. $\endgroup$ – Jernej Aug 11 '11 at 8:54
  • $\begingroup$ You cannot read much from the title of a talk - they may have just treated special cases, for example. $\endgroup$ – Chris Godsil Aug 11 '11 at 11:39
  • $\begingroup$ 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. $\endgroup$ – Jernej Aug 11 '11 at 15:16

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"



In addition to the good questions already given, let me add a reference to R. Hammack, W. Imrich, and S. Klav\v{z}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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.