25 problems

Parity-refined asymptotic conjecture. The limit of $n^2(\Delta-\lambda_1(G))$ always exists. Furthermore,

Extremal blowup conjecture. For any $j\geq 1$, we have

Let $n$ denote the order of a connected graph, and let the spectral sum be $\lambda_1(G)+\lambda_2(G)$, where $\lambda_1(G)$ and $\lambda_2(G)$ are the largest and second-largest a…

Extremal alpha-index and algebraic-connectivity conjecture. Given fixed $n\geq k+1$ and $k\geq 2$, the unique $k$-path graph that maximizes the $\alpha$-index for $\alpha\in[0,1]$…

Let $G$ be a connected graph with $n$ vertices, let $c(G)=e(G)-n(G)+\omega(G)$ be its cycle-space dimension, and let $S_2(G)$ denote the sum of the two largest signless Laplacian e…

Let a $(k,g,\underline{g+1})$-graph be a graph of degree $k$ and girth $g$ with no cycle of length $g+1$. The notation $(3,11,\underline{12})$ therefore denotes a cubic graph of gi…

Let $\mathcal{G}(n,\Delta)$ be the set of connected nonregular graphs of order $n$ with maximum degree $\Delta$ that attain the maximum spectral radius. Suppose $\Delta\geq 3$ and…

Liu–Li conjecture. Under these hypotheses, the degree sequence of $G$ has the stated form. Liu confirmed the conjecture for $\Delta=3,4$ and determined the exact structures in thos…

Positive $p$-energy path-minimization conjecture.

Let $G$ be a finite graph, let $K_q$ be the complete graph on $q$ vertices, and let $\hom(G,K_q)$ denote the number of graph homomorphisms from $G$ to $K_q$. Perkins–Perarnau's col…

Let $G$ be a regular graph, let $P_G(\lambda)$ denote its independence polynomial, and let $|V(G)|$ be its number of vertices. For a fixed degree and girth, let the corresponding M…

Minimum spectral radius conjecture. For every graph $G\in\mathbb{G}_{n,\lfloor\frac{n}{2}\rfloor}$,

Eventual parity-dependent degree-sequence conjecture. For each fixed $\Delta$ and sufficiently large $n$, $G$ has degree sequence $(\Delta,\ldots,\Delta,\delta)$, where

For integers $n$ and $g$, let $Lol_{n,g}$ be the graph obtained from a cycle with $g$ vertices by identifying one of its vertices with a vertex of a path of length $n-g$. It has…

Dumbbell-like graph conjecture. Dumbbell-like graphs $D_{a,b,a'}^{\ell}$ attain the minimum value of sum-Balaban index.

Balanced dumbbell conjecture. Among all dumbbell graphs $D_{a,b,a'}$ on at least $14$ vertices, the minimum value of sum-Balaban index is achieved for one with $a'=a$ or $a'=a+1$.

The extremal $K_4$-free graph conjecture. For $n\ge 10$, the $n$-vertex graph not containing $K_4$ that maximizes $\pi_f$ is $K_{1,\lfloor (n-1)/2\rfloor,\lceil (n-1)/2\rceil}$. Th…

Let $G$ be a bipartite graph on $n$ vertices. Write $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ for the complete bipartite graph whose parts have sizes $\lfloor n/2\rfloor$ and…

Conjecture. The source introduces a conjecture concerning extremal graphs for the remaining parity combinations of $n$ and $k$, but the supplied statement is incomplete and does no…

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…

For an extremal or largest known undirected circulant graph, let the type $T_1$ vertices be the vertices classified as type $T_1$ in the source's distance-partition analysis, and l…

Consider extremal and largest known undirected circulant graphs, arranged by degree and diameter, and partition their distance levels into a maximal zone, consisting of the levels…

Let $G$ be a simple graph on $n$ vertices, let $Q(G)=A+D$ be its signless Laplacian, and let $q_1(G),q_2(G)$ be the two largest eigenvalues of $Q(G)$. Set $S_2(G)=q_1(G)+q_2(G)$ an…

Let $G$ be a simple graph on $n$ vertices. Write $Q(G)=A+D$ for its signless Laplacian, let $q_1(G)$ and $q_2(G)$ be the two largest eigenvalues of $Q(G)$, and set…

Let $\kappa$ denote graph connectivity, and let $\mathcal{C}_4$ be the class of graphs for which every minor has connectivity at most $4$. Write $\widehat{\mathcal{C}}_4$ for the g…