13 problems

Almost-all-graphs cospectrality conjecture. The percentage of graphs that are not determined by their eigenvalues should rise to $100\%$ as the number of vertices increases; equiva…

Let $P_2(a,b)$ denote a double star, and let $K_{2,k}$ be the complete bipartite graph with parts of sizes $2$ and $k$. The complete-bipartite-subgraph conjecture. Graphs cospectra…

Let $P_2(a,b)$ denote a double star, and let graphs be cospectral when they have the same adjacency spectrum. The common-substructure conjecture. Graphs cospectral to these double…

Let $P_2(4,k)$ denote the double star with parameters $4$ and $k$, and let a cospectral mate be a nonisomorphic graph with the same spectrum. The cospectral-mate conjecture. For…

Let $G$ and $H$ be graphs, and suppose that a single similarity matrix establishes cospectrality of their generalized distance matrices for two distinct values of $q$, neither of w…

Let $G_1$ and $G_2$ be graphs with $B_1\subseteq V(G_1)$ and $B_2\subseteq V(G_2)$. Coalescing conjecture. If coalescing the same connected rooted graph onto every vertex of $B_1$…

Anđelić–da Fonseca–Simić–Du conjecture. There do not exist non-isomorphic cospectral connected chain graphs with respect to the adjacency spectrum.

Non-tree adjacency-spectrum determination conjecture. As the number of nodes increases, the fraction of non-tree graphs determined by their $A$-spectrum tends to one.

Haemers–Spence–Brouwer–Spence conjecture. Almost all graphs are likely to be determined by their spectrum.

Let $K_w$ be the complete graph on $w$ vertices, let $C_n$ be the cycle graph on $n$ vertices, and let $mC_n$ denote the disjoint union of $m$ copies of $C_n$. Write…

Let $F_n$ be a friendship graph, and let $G$ be a graph cospectral with $F_n$. Wang–Zhao–Huang conjecture. The minimum degree of $G$ is $2$. The source notes that the proofs in the…

For integers $p$ and $q$ with $q>2$, let $Kite_{p,q}$ denote the graph obtained by appending a complete graph $K_p$ to a pendant vertex of a path $P_q$. A graph is determined by ad…

Friendship graph spectral-determination conjecture. The friendship graph is $DS$; equivalently, if a graph $H$ has the same adjacency spectrum as $F_n$, then $H\cong F_n$.