# 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}$

-
Bounds in terms of what? –  Igor Rivin Oct 13 '11 at 20:16
Well, there is a bound in terms of "dual" Cheeger constant, which is not really computationally useful, and not what I'm looking for. Bound in terms of n and k would be ideal. But if there exist results in terms of other magnitudes defined on graphs, I would appreciate that information as well. –  Danijela Oct 13 '11 at 21:23
If the cardinality $\alpha$ of the largest independent set of vertices is an acceptable parameter, some manipulation of the Hoffman bound improves your "trivial bound" to $\lambda_n \geq k \frac{n}{n-\alpha}$. Is that useful? –  Clinton Conley Oct 13 '11 at 23:21

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.

-

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$.

-
Thanks, the first bound works nicely for my case. Could you give me a reference for the interlacing results you mention? –  Danijela Oct 14 '11 at 9:40
Section 2 of Willem Haemer's "Interlacing Eigenvalues and Graphs" (arno.uvt.nl/show.cgi?fid=2980 ) gives a short proof (the result itself goes back much further). The later sections of that paper also give many other applications of interlacing that may also be useful in getting bounds for your problem. –  Kevin P. Costello Oct 14 '11 at 20:34
I see. Its nothing but a Cauchy interlacing theorem. –  Danijela Oct 15 '11 at 15:08
$\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.