19 problems

A threshold graph is a graph obtained from an isolated vertex by repeatedly adding either an isolated vertex or a dominating vertex. Let $A_n$ denote the anti-regular graph on $n$…

Let $G$ be a finite simple graph with $n$ vertices and $m$ edges. Let $\mu_1(G)\geq\mu_2(G)\geq\cdots\geq\mu_n(G)=0$ be its Laplacian eigenvalues, and define … A threshold graph is…

Jamison and Sprague's conjecture. For every integer $k\ge 1$, there is a graph $G$ with

Let $G$ be a graph on $n$ vertices with $m$ edges and Laplacian eigenvalues $\mu_1\geq\mu_2\geq\cdots\geq\mu_n$, and define … For integers $k\in\{1,2,\cdots,n-1\}$, let $G_{k,r,s}$…

For each integer $n\geqslant 0$ and each vector $\bm{a}\in\{-1,0,1\}^n$, let $\mathcal{T}_{\bm{a}}$ be the associated signed threshold graph, with bivariate chromatic polynomial…

Let $n\geq 3$. For a threshold graph $G$ of order $n$, let $\mathcal{K}(G)$ denote its Kemeny constant, and let $r$ be one of the integers specified in the preceding proposition:…

Let $G$ be a threshold graph of order $n$, represented by a construction code, and let $\mathcal{K}(G)$ denote its Kemeny constant. Maximizing construction-code conjecture. The thr…

Signless Brouwer conjecture. For an integer $k$ with $1\leq k\leq n$,

Let $N>0$ and $r\geq 2$ be fixed, and let $I=(0,N]$. Let $T_G(a_1,\ldots,a_r)$ be the initial threshold graph obtained from RFI$(N,r)$. Minimality conjecture. The graph $G$ is mini…

Let $p$ be a prime and let $\alpha$ be a positive integer. Consider the group-annihilator graph realised by the group $\mathbb{Z}/p^{\alpha}\mathbb{Z}$. Hypoenergeticity conjecture…

Let $G$ be a graph, let $G^*$ denote its associated graph as defined in the paper, let ${\mathrm{th}}(G)$ be its threshold number, and let $\chi(G^*)$ be the chromatic number of…

Let $G$ be a threshold graph, let $A(G)$ denote its adjacency matrix, and let … The exceptional eigenvalues are $-1$ and, when present, $0$. Eigenvalue-free interval conjecture. Th…

Forbidden interval conjecture. The interval $\Omega$ is a forbidden eigenvalue interval for all threshold graphs: it contains no eigenvalues other than the trivial eigenvalues…

Spectral-importance conjecture. The spectral properties of anti-regular graphs with loops will play an important role within the class of threshold graphs with loops.

Forbidden-interval conjecture. The only eigenvalues of any threshold graph contained in $\Omega$ are $-1$ and/or $0$.

Let $k\geq 0$. Let $A$ be an almost alternating threshold graph, and let $G$ be a threshold graph with the same number of vertices and edges as $A$. Write $m_k(H)$ for the number o…

Maximal Laplacian energy conjecture. The graph $H_n$ has maximum Laplacian energy among all graphs on $n$ vertices.

Pineapple conjecture. Among all connected graphs on $n$ vertices, the pineapple maximizes the Laplacian energy.

Spectral threshold dominance conjecture. All graphs are spectrally threshold dominated.