21 problems

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

Regular extremal-structure conjecture. For every integer $d\ge3$, there exist constants $C_1$ and $C_2$ such that any $\mu$-minimal $d$-regular graph $G$ of order at least $C_1$ is…

Guiduli–Mohar conjecture. The graph $G$ is path-like, and, except for some blocks near each end, it has the same structure as Figure Mohar.

Guiduli–Mohar conjecture. If $n\equiv0\pmod{d+1}$, then the $\mu$-minimal graph on $n$ vertices with $\delta=d$ is the graph displayed in Figure Mohar.

Fix a surface $S$, and let $\mathcal{A}^{\infty}(S)$ denote the asymptotic algebraic connectivity associated with graphs on $S$. The double wheel graph is a graph whose algebraic c…

Let $G$ be a planar bichromatic graph, meaning a planar graph whose vertices can be coloured with two colours so that adjacent vertices have different colours. Let $a(G)$ denote it…

Let $G$ be a planar graph, and let $a(G)$ denote its algebraic connectivity, the second-smallest eigenvalue of its Laplacian. The graphs $K_4$ and $2K_1\dot{+}C_4$ are the complete…

Extremal algebraic-connectivity conjecture. Given fixed $n\geq k+1$ and $k\geq 2$, the unique $k$-path graph that maximizes the algebraic connectivity is $K_{k-1}\vee P_{n-k+1}$. M…

Let $a(G,X)$ denote the algebraic connectivity of a graph $G$ in a normed space $X$, let $K_{2d}$ be the complete graph on $2d$ vertices, and let $T_d$ be the tree defined in the p…

Let $d\geq 1$ and $k\geq 2$. For positive integers $n_1,\ldots,n_k$, write $n=n_1+\cdots+n_k$, and let $K_{n_1,\ldots,n_k}$ be the complete $k$-partite graph whose sides have sizes…

Algebraic-connectivity monotonicity conjecture. The function $f(g;d,n)$ is increasing as a function of $g$.

Maximum-connectivity–girth conjecture. For fixed degree $d$ and order $n$, a graph maximizing $AC(G)$ also has maximum possible girth.

For $d\geq 1$, let the maximum range over all $2d$-regular graphs $G$ on $n$ vertices be taken. Regular-graph vanishing conjecture. … This is presented as a possible generalization…

Let $a_d(K_n)$ denote the parameter associated with $d$-dimensional algebraic connectivity for the complete graph $K_n$. Complete-graph tightness conjecture. If $n\geq 2d$, then ……

For each $n\ge 11$, let $\mathcal{G}_n$ be the quartic graph of order $n$ constructed from the blocks displayed in the paper, and call a quartic graph minimal when it has minimum s…

Quartic minimum-gap conjecture. The connected quartic graph on $n\geq 11$ vertices with minimum spectral gap is the unique graph $G$ described as follows: $G$ consists of $q$ middl…

Aldous–Fill spectral-gap conjecture. The spectral gap of a connected $k$-regular graph on $n$ vertices is at least

Let $G$ be a cubic graph, and let $D$ be its diameter. The cubic-graph algebraic-connectivity bound conjecture. Its algebraic connectivity satisfies … Moreover, if $G$ has order…

Let $T$ be a tree with … vertices and maximum degree $d$. The well-balanced Bethe tree extremal conjecture. Its algebraic connectivity is less than the algebraic connectivity of th…

Let $T$ be a tree with $n$ vertices and maximum degree $d$. The asymptotically optimal tree bound conjecture. As $n\rightarrow\infty$ for fixed $d$, … Here $\lambda_{2}(T)$ denotes…

Let $G$ be a graph with exactly $n$ vertices and $m=2(n-2)$ edges. The complete-bipartite extremal conjecture. Among all such graphs, a graph maximizing the algebraic connectivity…