37 problems

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

Let $G$ be a finite transitive graph, let $|G|$ denote its number of vertices, and let $p^G$ be its percolation threshold. Diameter criterion conjecture. There is a constant $C<1$…

Critical-exponent conjecture. (A) If $s=2$, then the diameter's order of magnitude is $N^\delta$, where $\delta$ is a function of $\beta$. (B) If $1<s<2$, then the diameter is…

Let $r,\delta\geq2$ be fixed integers, and let $G$ be a connected graph of order $n$ and minimum degree $\delta$. Erdős–Pach–Pollack–Tuza conjecture. (i) If $G$ is $K_{2r}$-free an…

Minimum-degree diameter conjecture. For every $d\geq3$ and $\epsilon0$,

Stochastic diameter monotonicity conjecture. If

Let $C\!D(k,q)$ be a connected component of $D(k,q)$. Schneider's conjecture. For every prime power $q$, $\operatorname{diam}(C\!D(3,q))=6$. For $k>3$ odd, the diameter is $k+5$, a…

Let $C\!D(k,q)$ be a connected component of $D(k,q)$, with $k\ge 2$ and $q$ a prime power. Lazebnik–Ustimenko–Woldar's conjecture. There is a positive constant $C$ such that … This…

Repetition-ratio conjecture. For every $\delta\geq4$,

Czabarka–Singgih–Székely conjecture. If $\omega(G)\leq k$, then

Let $K_n$ be the complete graph on $n$ vertices, and let $\mathcal{U}(K_n)$ be its unlabelled inversion graph, obtained by identifying vertices of the inversion graph corresponding…

Let $G$ be a graph, let $t$ be a positive integer, let $\overline{K}_t$ be the edgeless graph on $t$ vertices, and let $G[\overline{K}_t]$ denote the blow-up of $G$ in which each v…

Let $G$ be a graph, let $\mathcal{I}(G)$ be its inversion graph, and let $\Delta(G)$ denote its maximum degree. Inversion diameter conjecture. For every graph $G$, … This would giv…

Laplacian eigenvalue distribution conjecture. If $c=0,\dots,d-2$ and

Let $G$ be a graph, with Randić index $\operatorname{R}(G)$, diameter $\operatorname{d}(G)$, and order $\#V(G)$. Aouchiche–Hansen's conjectured bound. … This is a proposed lower bo…

Let $G$ be a connected graph of order $n$, let $d$ be its diameter with $d\ge 2$, and let $m_GI$ denote the number of Laplacian eigenvalues of $G$ in an interval $I\subseteq[0,n]$.…

Let $Y$ be a graph on $n$ vertices, and let $\mathsf{FS}(\textsf{Cycle}_n,Y)$ denote its friends-and-strangers graph. The quadratic diameter conjecture asserts that the maximum dia…

Let $k$ and $r$ be integers with $2\leq r\leq k-2$, and let $D(G)$ denote the diameter of a graph $G$. For $n=2k+r$, write $\operatorname{SG}(n,k)$ for the Schrijver graph. Unit-ga…

Let $k$ and $r$ be integers with $r\geq 1$, and let $D(G)$ denote the diameter of a graph $G$. For $n=2k+r$, write $\operatorname{SG}(n,k)$ for the Schrijver graph. Monotonicity co…

Czabarka–Dankelmann–Székely conjecture. For every such $G$,

Let $G$ be a cactus with $k$ cycles and $b$ bridges; write $n$ for its number of vertices, $R$ for its Randić index, and $d$ for its diameter. A BC-tree is the block-cut tree of…

Let $G$ be a graph with $n$ vertices. Write $R=R(G)$ for its Randić index and $d$ for its diameter. Aouchiche's conjecture. The two bounds … and … should hold. These inequalities c…

Let $GPG(n,s)$ be the generalized Petersen graph and let $C_n(1,s)$ be the circulant graph with step sizes $1$ and $s$. Let $n\geq 5$ and…

Bipartite bounded-diameter conjecture. There is an integer $d$ such that, for every $r\geq 2$, every $r$-coloring of every $K\in\mathcal{K}_2$ has a monochromatic cover of order at…

Modified diameter conjecture. Under either the $K_{k+1}$-free hypothesis, or the weaker $k$-colorable hypothesis, one should have