Guiduli–Mohar conjecture on minimum algebraic connectivity with prescribed minimum degree

Let HH be a connected graph of order nn with minimum degree δ(H)=d\delta(H)=d, and let μ(H)\mu(H) denote the second-smallest eigenvalue of its Laplacian. A graph is μ\mu-minimal with minimum degree dd if it has the smallest algebraic connectivity among all such graphs.

Guiduli–Mohar conjecture. If n0(modd+1)n\equiv0\pmod{d+1}, then the μ\mu-minimal graph on nn vertices with δ=d\delta=d is the graph displayed in Figure Mohar.

The conjecture predicts an explicit path-like block structure for extremal graphs; the cited figure specifies that structure, including complete-graph blocks. Its general status is not resolved in the supplied text.

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).

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.