Bounds on maximal eigenvalue of a k-regular graph 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}$
 A: 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$.  
A: 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.
A: $\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.
