8
$\begingroup$

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:

$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$

This bound is very elegant but it is not very strong, as far as I can tell (for example, among the 11117 connected graphs on 8 vertices it only achieves the value $3$ for fifty (50) graphs, whereas there are actually 6962 graphs whose diameter is at least three; even for those fifty graphs, the estimate is not sharp, as they all actually have diameter at least 4).

Are there known bounds of this kind which significantly improve upon the Mohar-McKay bound?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

I believe the bound is sharp for $K_n$ and $P_3$.

There aren't other small sharp cases according to my search.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .