An upper bound for the largest Laplacian eigenvalue of a graph in terms of its diameter

Let $$G$$ be a simple graph with $$n$$ vertices and $$\lambda$$ be the largest eigenvalue of its Laplacian operator $$L=D-A$$. I have some evidence for the following conjecture:

Conjecture: If G has diameter $$\delta>3$$ then $$\lambda\leq n-1$$.

I need a proof or a counterexample for this conjecture. Does there exist a good general upper-bound for $$\lambda$$ in terms of $$\delta$$ which includes the above conjecture (if it is true)?

• What are $D$ and $A$? – Ilya Bogdanov Nov 21 '18 at 10:50
• @IlyaBogdanov: It seems that $A$ is the adjacent matrix of $G$ and $D$ is a diagonal matrix whose diagonal entries are degrees of the vertices of $G$. – Mahdi Nov 21 '18 at 11:29
• For any graph, the largest eigenvalue of the Laplacian sastisfies $\lambda \leq 2$ (see e.g. Lemma 1.7 (v) in math.ucsd.edu/~fan/research/cb/ch1.pdf). So $\lambda \leq n-1$ for $n\geq 3$. Since the remaining cases have diameter at most $1$, doesn't that prove the conjecture? – Arnaud Nov 21 '18 at 11:40
• @Arnaud: $\lambda \le 2$ for the eigenvalues of the normalized Laplacian $I - D^{-1/2}AD^{-1/2}$. – Ivan Izmestiev Nov 21 '18 at 11:48
• @IvanIzmestiev: Thanks, I had the feeling that something was amiss. – Arnaud Nov 21 '18 at 11:54

I have not been able to conclude, but I think the following is a good start. (EDIT: the proof should be complete now)

Because the diameter is at least $$4$$, there exist $$x,y$$ with $$d(x,y)\geq4$$. In particular for all $$z$$ , $$d(x,z)+d(y,z)\geq4$$ We recall that $$\lambda=\frac{1}{2}\max_{\sum|u(i)|^{2}=1}\sum_{i\sim j}(u(i)-u(j))^{2}$$ and therefore is monotone increasing in the edges. To consider the maximum of $$\lambda$$, it is enough to study the maximal graphs $$G=(V,E)$$ with $$d(x,y)=4$$. We can then suppose that for all $$z$$: $$d(x,z)+d(y,z)=4$$. (Indeed if for example $$d(x,z)\geq3$$ (resp. $$d(y,z)$$) let $$z'$$ such that $$d(x,z')=2$$, we can add the edges $$(z,y)$$ and $$(z,z')$$ to our graph).

Let us call $$A=\text{\{}z:d(x,z)=1\text{\}}$$

$$B=\text{\{}z:d(x,z)=2\text{\}}$$

$$C=\text{\{}z:d(x,z)=3\text{\}}$$ Because of the maximality of $$G,$$ we have $$V=A\cup B\cup C\cup\text{\{}x,y\text{\}}$$ $$E=\text{\{}(x,z):z\in A\text{\}}\cup\text{\{}(z_{1},z_{2}):z_{1},z_{2}\in A\cup B\text{\}}\cup\text{\{}(z_{1},z_{2}):z_{1},z_{2}\in B\cup C\text{\}}\cup\text{\{}(y,z):z\in C\text{\}}.$$

Let us now consider the following orthonormal family : $$1_{\text{\{}x\text{\}}},1_{\text{\{}y\text{\}}},u_{A}=\frac{1_{A}}{\sqrt{|A|}},u_{B}=\frac{1_{B}}{\sqrt{|B|}},u_{C}=\frac{1_{C}}{\sqrt{|C|}}$$. We have

$$\begin{cases} L(1_{\text{\{}x\text{\}}})=|A|1_{\text{\{}x\text{\}}}-1_{A}\\ L(1_{A})=-|A|1_{\text{\{}x\text{\}}}-|A|1_{B}+(1+|B|)1_{A}\\ L(1_{B})=-|B|1_{A}-|B|1_{C}+(|A|+|C|)1_{B}\\ L(1_{C})=-|C|1_{\text{\{}y\text{\}}}-|C|1_{B}+(1+|B|)1_{C}\\ L(1_{\text{\{}y\text{\}}})=|C|1_{\text{\{}y\text{\}}}-1_{C}. \end{cases}$$

This gives in the family $$(1_{\text{\{}x\text{\}}},u_{A},u_{B},u_{C},1_{\text{\{}y\text{\}}})$$ the following matrix

$$M=\begin{pmatrix}|A| & -\sqrt{|A|} & & 0 & 0\\ -\sqrt{|A|} & |B|+1 & -\sqrt{|A||B|} & & 0\\ & -\sqrt{|A||B|} & |A|+|C| & -\sqrt{|B||C|}\\ 0 & & -\sqrt{|B||C|} & |B|+1 & -\sqrt{|C|}\\ 0 & 0 & & -\sqrt{|C|} & |C| \end{pmatrix}$$ Actually we can write $$L$$ as the block matrix $$L=\begin{pmatrix}M & 0\\ 0 & L' \end{pmatrix}$$ EDIT (2) :We note $$p$$ the orthonormal projector on $$(1_{\text{\{}x\text{\}}},u_{A},u_{B},u_{C},1_{\text{\{}y\text{\}}}) )^\perp$$ and with a small abuse on notation we denote $$L'=pLp$$. Let $$a\in A$$ then $$L(1_{a})=-1_{x}-1_{B}-1_{A}+(|A|+|B|)1_{a}$$. We have $$p(1_{a})=1_{a}-\frac{1}{\sqrt{A}}u_{A}$$ and therefore $$pLp(1_{a})=(|A|+|B|)(1_{a}-\frac{1}{\sqrt{A}}u_{A})$$. Similar for $$b\in B$$ and $$c\in C$$. Finally we have for any $$v$$ $$\langle v, pLp v\rangle=(|A|+|B|)\big(\sum_{a\in A} |v(a)|^2-\frac{1}{|A|} (\sum_{a\in A} v(a) )^2\big)+(|A|+|B|+|C|-1)\big(\sum_{b\in B} |v(b)|^2-\frac{1}{|B|} (\sum_{b\in B} v(b) )^2\big)+(|B|+|C|)\big(\sum_{c\in C} |v(c)|^2-\frac{1}{|C|} (\sum_{c\in C} v(c) )^2\big)$$ which is smaller than $$(|A|+|B|+|C|-1)\|v\|^2$$

So we only have to deal with $$M$$. The problem can be state as follow :Do we have $$\|M\|\leq|A|+|B|+|C|+1$$?

Here is where I get stuck. It should be possible to do a complete analysis of $$M$$ and calculate explicitely the largest eigenvalue but it seems a bit tedious. We can also make some numerical simulations : no counter example appear for $$|A|+|B|+|C|\leq 100$$

EDIT (end of the proof)

To finish the proof, we show that

$$|A|+|B|+|C|+1-M=\begin{pmatrix}|B|+|C|+1 & \sqrt{|A|} & 0 & 0 & 0\\ \sqrt{|A|} & |A|+|C| & \sqrt{|A||B|} & 0 & 0\\ 0 & \sqrt{|A||B|} & |B|+1 & \sqrt{|B||C|} & 0\\ 0 & 0 & \sqrt{|B||C|} & |A|+|C| & \sqrt{|C|}\\ 0 & 0 & 0 & \sqrt{|C|} & |A|+|B|+1 \end{pmatrix}$$

is a positive matrix, computing all its minors determinants. Computations gives (notation :$$|A|=a,|B|=b,|C|=c$$):

$$m_{1}=b+c+1$$

$$m_{2}=ab+ac+bc+c^{2}+c$$ $$m_{3}=ac+b^{2}c+bc^{2}+2bc+c^{2}+c$$

$$m_{4}=a^{2}c+2abc+2ac^{2}+ac+bc^{2}+c^{3}+c^{2}$$ $$m_{5}=a^{3}c+3a^{2}bc+2a^{2}c^{2}+2a^{2}c+2ab^{2}c+3abc^{2}+3abc+ac^{3}+2ac^{2}+ac$$ and they are all positive.

• Just apply the Schur test with the test vector $[|A|,(|B|+1)\sqrt{|A|},(|A|+|C|)\sqrt{|B|}, (|B|+1)\sqrt{|C|}, |C|]^T$ to check the desired bound. – fedja Nov 22 '18 at 20:56
• Could you please give the detailed proof for the estimate on the eigenvalues of $L'$? I don't understand the usage of max- min principle here. – Mostafa Nov 23 '18 at 19:37