Let $G=(E,V)$ be a simple graph. The graph Laplacian is given by $$ L= D-A,$$ where $D$ is the degree matrix (diagonal matrix with entries corresponding to the degree of the vertex) and $A$ the adjacency matrix. Denote with $G_{nm}$ the $n\times m$ grid graph Example grid graph $G_{66}$. We like to label the vertices row by row with $1,2,...,m,m+1,...,m \cdot n$ . The Laplacian spectra of a grid graph is well understood. The eigenvalues are $$ \lambda_{ij} = 4\sin^2\left(\frac{(i-1)\pi}{2 n }\right)+4\sin^2\left(\frac{(j-1)\pi}{2 m }\right) $$ for $i\in\{1,...,n\}$ and $j\in\{1,...,m\}$. The corresponding eigenvectors $u_{ij}$ (with normalization $\langle u_{ij}, u_{ij}\rangle = 1$) are $$ u_{ij}:(x,y)\mapsto \frac{A_iB_j}{\sqrt{nm}}\cos\left[\left(x-\frac{1}{2}\right)\frac{i\pi}{n} \right] \cos\left[\left(y-\frac{1}{2}\right)\frac{j\pi}{m} \right] $$ for $x\in \{1,...,n\}$ and $y\in\{1,...,m\}$ where $A_i=1,B_j=1$, except $A_1=B_1 =\frac{1}{\sqrt{2}}$.

See:
*Pozrikidis, C.*, An introduction to grids, graphs, and networks, Oxford: Oxford University Press (ISBN 978-0-19-999672-8/hbk). xii, 284 p. (2014). ZBL1330.00004. - Chapter 3, spectra of lattices.

This can be easy understood since the problem factorizes - The grid graph $G_{nm}$ can be written as the Cartesian product of the path graphs $P_n$ and $P_m$: $G_{nm}=P_n\square P_m$ . In terms of spectra it holds $$ \mathrm{spec}(L(G_{nm}))=\mathrm{spec}(L(P_{n}))\oplus \mathrm{spec}(L(P_{m})). $$

**Problem:**

Now consider the graph $S_{n}$ as the graph resulting from $G_{nn}$ by deleting the "diagonal" vertices labeled by $1,n+2,2n+3,...,n\cdot n$. The graph $S_n$ has two connected components (see picture connected components of $S_n$). As both connected components are the same, I will call the connected component again $S_n$.

**I am now interested in the spectrum of $S_n$. Is there any analytic solution to the Laplacian eigenvalue problem for $S_n$?. In particular I want to know the behavior of the first nonzero eigenvalue in function of $n$ (exponential vs. polynomial decrease?).**

As I could figure out so far, it holds $$ \mathrm{spec}(L(P_n))\subseteq \mathrm{spec}(L(S_n)). $$ This comes from the fact that the superposition $\frac{1}{\sqrt{2}}\left(u_{i1}+u_{1i}\right)$ (projected to the corresponding subspace of vertices from $S_n$) is again a eigenvector of $L(S_n)$ with same eigenvalue $\lambda_{i1}$ for all $i\in \{1,...,n\}$. My guess for the smallest nonzero Laplacian eigenvalue of $S_n$ would be $ 4\sin^2\left( \frac{\pi}{2n}\right)$.

**Generalization to higher dimensions**

Also of interest is the same problem generalized to higher dimensions. The connected components of $S_n$ can be produced by starting with a path graph $P_{n-1}$ and "adding" a shorter row $P_{n-2}$ next to it, and repeat this procedure until reach the trivial graph $P_1$. As a generalization to the 3D case consider $S_{n-1}$ and "add" another layer of $S_{n-2}$ next to it and so on ( See: 3D generalization). Also this graph can be constructed by starting from the 3D grid graph $G_{nnn}$ and deleting vertices along 3 hyperplanes. (Example $G_{666}$, The 6 connected components after cutting out vertices of $G_{666}$ ) Also in this case, calculations in mathematica suggest that the lowest nonzero eigenvalue of the connected components is again $ 4\sin^2\left( \frac{\pi}{2n}\right)$ (checked it for small $n$ up to 10.)

Many thanks in advance. Martin :)