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)?



An upper bound for the largest Laplacian eigenvalue of a graph in terms of its diameter
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.


