Conjecture that asymptotically minimum algebraic connectivity implies maximum diameter

At least 3 years old · documented by

Let d≥3d\ge3, and let Γn\Gamma_n be a sequence of graphs with minimum degree δ=d\delta=d, or a sequence of dd-regular graphs. Say that the sequence has asymptotically minimum algebraic connectivity if its algebraic connectivity is asymptotically the smallest possible in the relevant class, and asymptotically maximum diameter if its diameter is asymptotically maximal.

Minimum-connectivity–maximum-diameter conjecture. If Γn\Gamma_n has asymptotically minimum algebraic connectivity, then its diameter is asymptotically maximum, namely

diam⁡(Γn)=(1+o(1))3nd+1.\operatorname{diam}(\Gamma_n)=(1+o(1))\frac{3n}{d+1}.

The paper proves that maximum diameter does not generally force asymptotically minimum algebraic connectivity for larger degrees, while proposing this converse direction as a general principle.

References

Primary source

Maryam Abdi and Ebrahim Ghorbani, “Minimum algebraic connectivity and maximum diameter: Aldous–Fill and Guiduli–Mohar conjectures”, arXiv:2212.03571 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.