Spectral Graph Theory :Cartesian product of Laplace Matrix

Question

Let $G\times H$ be the Cartesian Product of $G$ and $H$.

Determine $L(G\times H)$ in terms of $L(G)$ and $L(H)$ where $L(G) $ denotes Laplacian Matrix of $G$.

Also find the eigen values of $L(G\times H)$ in terms of $L(G)$ and $L(H)$.

My try:

Let $|V(G)|=n;|V(H)|=m$ .Then $|V(G\times H)|=m\times n$.

Now two vertices $(v,w)\sim (v_1,w_1)\iff v\sim v_1 \text{and} w\sim w_1$.

I am unable to understand how the $(i,j)^{th}$ entry of $L(G\times H)$ will look.

Please give some hints. I am unable to solve the problem.

Answer 1

Important properties of Kronecker product operation: $$(A\otimes B)(C\otimes D)=AC\otimes BD,$$ $$A\otimes(B+C)=A\otimes B+A\otimes C.$$ Now if $L(G)X_i=\lambda_i X_i$ and $L(F)Y_j=\mu_j Y_j$, then \begin{align*}L(G\times H)(X_i\otimes Y_j)&=(L(G)\otimes I_m+I_n\otimes L(H))(X_i\otimes Y_j)\\&=L(G)X_i\otimes I_mY_j+I_nX_i\otimes L(H)Y_j\\&=\lambda_iX_i\otimes Y_j+\mu_jX_i\otimes Y_j\\&=(\lambda_i+\mu_j)X_i\otimes Y_j.\end{align*}