Conjecture that asymptotically minimum algebraic connectivity implies maximum diameter

From papers

Let d3d\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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.