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?

$\endgroup$
0

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.