Question

Given a k-regular graph $G$ (every vertex is of degree k), one defines its Laplace operator as $L(G)=D-A=kI-A$, where $I$ is identity matrix and $A$ adjacency matrix of $G$. Let $\lambda_{1}\leq \ldots \leq \lambda_{n}$ be eigenvalue of $L(G)$, are there any results on lower bound on $\lambda_{n}$. Of course, here I have in mind bounds other than a trivial one: $k\frac{n}{n-1}\leq \lambda_{n}$

Answer 1

Even though the question has been answered, I feel I should flesh out my comment into an answer. Apologies for the redundancy.

First, here's a simple proof of this special case of the Hoffman bound. Suppose $X$ is an independent set of vertices of $G$ (some call this a coclique) of cardinality $\alpha$. Let $\mathbf{x} = (x_1, \ldots, x_n)$ be the characteristic function of $X$, so $x_i = 1$ if the $i$th vertex is in $X$, and $x_i = 0$ if it isn't in $X$. Put $\mathbf{y} = \mathbf{x} - \frac{\alpha}{n} \mathbf{1}$.

Direct computation shows that $\langle \mathbf{y}, \mathbf{y} \rangle = \alpha - \frac{\alpha^2}{n}$. A slightly more bothersome calculation (using the fact that $\langle A \mathbf{x}, \mathbf{x} \rangle = 0$) shows that $$ \langle L\mathbf{y}, \mathbf{y} \rangle = k\langle \mathbf{y}, \mathbf{y} \rangle - \langle A\mathbf{y}, \mathbf{y} \rangle = k\left(\alpha - \frac{\alpha^2}{n}\right) - \left(0 - 2\frac{k \alpha^2}{n} + \frac{k\alpha^2}{n} \right) = k\alpha. $$ Finally, since $\langle L \mathbf{y}, \mathbf{y} \rangle \leq \lambda_n \langle \mathbf{y}, \mathbf{y} \rangle$, we see $\lambda_n \geq k \frac{n}{n-\alpha}$ as desired.

Note in particular that since any graph which is regular of degree $k$ is $(k+1)$-colorable, there is an independent set of cardinality at least $\frac{n}{k+1}$. Plugging this in for $\alpha$ recovers the $\lambda_n \geq k+1$ bound shown by Kevin in his answer.

Answer 2

$\lambda_n = k - \mu_1$, where $\mu_1$ is the least (most negative) eigenvalue of the adjacency matrix. That eigenvalue is well studied, so that is where to search. For example $\mu_1\le -1$, hence $\lambda_n\ge k+1$, and all graphs with $\mu_1\ge -2$ are known. They include all line graphs, so $k+1\le\lambda_1\le k+2$ for all regular line graphs. On the other hand, $\lambda_1\le 2k$ with equality iff $G$ is bipartite.

There are references to more bounds here, see the end of page 57.

Answer 3

We'll work with $A$, then translate our results to bounds on $L$ at the end. Suppose the eigenvalues of $A$ are $k=\alpha_1 \geq \dots \geq \alpha_n$. Since $A$ has zero trace, we have $$\alpha_1+\alpha_2+\dots+\alpha_n=0.$$ The sum of the squares of the eigenvalues is equal to $Tr(A^2)$, which counts the number of closed walks of length $2$ on $G$. There are $k$ such walks starting at each vertex, so we have $$\alpha_1^2+\alpha_2^2+\dots+\alpha_n^2=kn.$$ Now by assumption we have that every $\alpha_i$ lies in $[\alpha_n, k]$. It follows from the convexity of $x^2$ that $$kn=\alpha_1^2+\dots+\alpha_n^2 \leq n(p*\alpha_n^2+(1-p)*k^2),$$ where $0\leq p\leq1$ is chosen such that $\alpha_n p + (1-p) k=0=\sum \alpha_i$.

Direct computation gives that $p=\frac{k}{k-\alpha_n}$. Plugging this into the above equation and solving for $\alpha_n$ gives $\alpha_n^2 \geq 1$, so $\alpha_n \leq -1$. Translating back to the Laplacian gives $\lambda_n \geq k+1$ independent of $n$.

This is tight for the case where $G$ consists of the union of disjoint copies of $K_{k+1}$. If you have more information on the structure of $G$, you may be able to get a better bound by translating that into a bound on the number of closed walks of length $3$ or $4$ on $G$ (the sum of $\alpha_i^3$ or $\alpha_i^4$).

An alternative argument which might provide better bounds in some cases is to use interlacing: If $H$ is any induced subgraph of $G$, the minimal (adjacency) eigenvalue of $H$ is at least as large as the minimal (adjacency) eigenvalue of $G$. For example, if $G$ contains a vertex not contained in any triangle, then you can take $H$ to be the $k-$star induced by that vertex and its neighborhood to get a $k+\sqrt{k}$ bound on $\lambda_n$.