1,151 problems

Alon's spectral-radius conjecture. For every $\varepsilon>0$,

Brouwer's conjecture. For every $k\in\{1,2,\dots,n\}$,

Let $\alpha_{1,k}$ denote the asymptotic extremal constant studied in the paper for the relevant sums of adjacency eigenvalues of a graph and its complement. Proposition gives a lo…

Let $G$ be a graph on $n$ vertices, and let $\overline G$ denote its complement. Write $\lambda_1(G)$ for the largest adjacency eigenvalue of $G$. Nikiforov's conjecture. One has ……

Let $\mathcal P_m(n)$ be the generalised pancake graph and let $Q(\mathfrak P_{m,n})$ be the associated matrix used in the paper. For a symmetric matrix or graph, write $\lambda_1$…

Haemers' conjecture. The fraction of graphs on $n$ vertices with an $M$-cospectral mate tends to zero as $n$ tends to infinity.

Let $\Gamma$ be a connected graph on $[n]=\{1,2,\ldots,n\}$, and identify each edge of $\Gamma$ with the corresponding transposition of $S_n$. Write $T(\Gamma)$ for the resulting s…

Let $G$ be a non-complete graph on $n$ vertices with $m$ edges, adjacency eigenvalues $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n$, and clique number $\omega=\omega(G)$. Bollobás–N…

Let $G$ be a $d$-regular graph, let $A_\sigma$ be the signed adjacency matrix associated with a signing $\sigma$ of $G$, and write $\rho(A_\sigma)=\max_i|\lambda_i(A_\sigma)|$. Bil…

Throughout, let $F$ be a graph, and let $\operatorname{Ex}(n,F)$ be the set of $n$-vertex $F$-free graphs maximizing the number of edges, while…

Gutman et al.'s conjecture. For any graph $G$ of order $n$,

Alon–Krivelevich–Sudakov conjecture. The condition

Let $A_n$ denote the adjacency matrix of $WS_n(K_n,p_n)$, where … and suppose that $K_np_n\xrightarrow[n\to\infty]{}C$ for a constant $C\in(0,\infty)$. Finite-degree limiting spect…

Cheeger-constant Nordhaus-Gaddum conjecture. If $G\neq S_n$, then

Let $\mathcal{G}$ be a fixed $k$-regular graph and let $\mathcal{G}_p$ be a random lift of degree $p$. Denote by $\lambda_{\mathrm{new}}(\mathcal{G}_p)$ the maximum absolute value…

Let $G$ be a connected graph on $n$ vertices. Define its positive and negative square energies by … where $\lambda_1,\ldots,\lambda_n$ are the adjacency eigenvalues of $G$. Elphick…

Let $G$ be a connected graph on $n\geq 3$ vertices, let $k$ be its matching number, and let $\rho(G)$ denote its spectral radius. Aouchiche–Hansen conjecture. Based on extensive co…

Let $G$ be an $(n,d,lambda)$-graph, meaning a $d$-regular graph on $n$ vertices whose non-trivial adjacency-matrix eigenvalues have absolute value at most $lambda$. Krivelevich–Sud…

Let $G$ be an outerplanar graph on $n$ vertices, let $\lambda(G)$ denote the spectral radius of its adjacency matrix, let $P_{n-1}$ be the path on $n-1$ vertices, and let $\vee$ de…

Let $G$ be a finite simple connected graph of order $n=|V(G)|\ge2$. For each vertex $v$, let $d(v)$ be its degree and $N(v)$ its open neighbourhood, and define … Let $D(G)$ be the…

Second-largest eigenvalue conjecture. If $\mu$ has at least two parts of size $1$, or if $\mu=[n-1,1]$ with $n\neq 4$, then the second largest eigenvalue of $A_\mu$ occurs on the i…

Let $G$ be a triangle-free graph, let $\chi(G)$ denote its chromatic number, and let $\rho(G)$ denote its spectral radius. Spectral-radius chromatic bound. Every triangle-free grap…

Let a graph be determined by its adjacency spectrum if every graph with the same adjacency eigenvalue multiset is isomorphic to it. Van Dam–Haemers conjecture. Almost all graphs ar…

Let $G$ be a planar graph on $n$ vertices, let $\lambda(G)$ denote the spectral radius of its adjacency matrix, let $P_{n-2}$ be the path on $n-2$ vertices, and let $\vee$ denote g…

Exact spectral threshold conjecture. If