Conjecture that asymptotically minimum algebraic connectivity implies maximum diameter
Conjecture that asymptotically minimum algebraic connectivity implies maximum diameter
Let , and let be a sequence of graphs with minimum degree , or a sequence of -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 has asymptotically minimum algebraic connectivity, then its diameter is asymptotically maximum, namely
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
Sign in to submit a solution.
No solutions have been posted yet.