22 problems

For an integer set $I$, let $\mathcal{C}_I$ denote the family of cycles whose lengths belong to $I$, and let $\operatorname{sat}(n,\mathcal{C}_I)$ be the minimum number of edges in…

For an integer set $I$, let $\mathcal{C}_I$ denote the family of cycles whose lengths belong to $I$, and let $\operatorname{sat}(n,\mathcal{C}_I)$ be the minimum number of edges in…

Let $\mathcal{C}_I$ denote the family of cycles whose lengths belong to an integer set $I$, and let $\operatorname{sat}(n,\mathcal{C}_I)$ be the minimum number of edges in an $n$-v…

For a positive integer set $I$, let $\mathcal{C}_I$ denote the family of cycles whose lengths belong to $I$, and let $\operatorname{sat}(n,\mathcal{C}_I)$ be the minimum number of…

Uniquely $C_{4}^{+}$-saturation conjecture. A graph $G$ is nontrivial uniquely $C_{4}^{+}$-saturated if and only if $G$ is a strongly regular graph with parameters $(n,k,0,2)$ or…

Double-star conjecture. Double stars are the only trees $T$ for which nontrivial uniquely $T$-saturated graphs exist.

For integers $r\geq 3$ and $t\geq r$, let $e_{r,t}(s)$ and $e_{r,t}'(s)$ be the minimum number of edges in the underlying graph of an $(r,t)$-system and a maximal $(r,t)$-system, r…

For integers $r\geq 3$, $t\geq r-2$, and $m\geq 0$, let $s_{r,t}(m)$ be the maximum size of the family in an $(r,t)$-system $(H,\mathcal{F})$ with $|H|=m$. An extremal system is on…

Let $\operatorname{tsat}(n,K_r,t)$ denote the minimum number of edges in a twin-free $K_r$-saturated graph on $n$ vertices with minimum degree at least $t$. A vertex is conical if…

Let $r$ and $t$ be integers with $r\geq 3$ and $t\geq r$. For an $(r,t)$-system $(H,\mathcal{F})$, let $e_{r,t}(s)$ be the minimum of $e(H)$ over systems with $|\mathcal{F}|=s$, an…

Let $r\geq 4$ and $t\geq r-2$ be integers. Let $C(r,t)$ denote the family of graphs defined by $C(r,t)=C(r,t,-c(r,t))$, where $c(r,t)$ is the corresponding extremal constant for…

Kim–Kim–Kostochka–O conjecture.

Chakraborti–Loh uniqueness conjecture. The graph $K_{s-2}+\overline{K_{n-s+2}}$ is the unique $n$-vertex $K_s$-saturated graph minimizing the number of copies of $C_r$. This is a p…

Let $t$ be an integer with $t\geq 4$. For an $n$-vertex $K_4$-saturated graph, let $\operatorname{sat}_t(n,K_3,K_4)$ denote the minimum number of triangles among graphs with minimu…

Fuller–Gould conjecture. The $K_4^-$-saturated graphs with sizes in the interval

Let $g_r(n,m)$ denote the maximum number of vertices that one is required to remove from an $n$-vertex, $(r+1)$-saturated graph with at least $t_r(n)-m$ edges so that the remaining…

Nonexistence conjecture. For $t\ge 6$, there are no nontrivial uniquely $C_t$-saturated graphs.

For fixed $t$, define $c(t,3)$ by … for all sufficiently large $n$. The preceding construction gives a lower bound of order $2^{t}t^{3/2}$ for $c(t,3)$. The asymptotic bound conjec…

The extremal bound conjecture. If $n$ is large, then every $\{2,4\}$-saturated graph $G$ on $n$ vertices satisfies

Let $r\geq 3$. An $r$-primitive graph is a uniquely $K_r$-saturated graph with no dominating vertex. Finiteness conjecture. For each $r\geq 3$, there are a finite number of $r$-pri…

Regularity conjecture. For each $r$, a uniquely $K_r$-saturated graph with no dominating vertex is regular.

Finiteness conjecture. For each $r$, there are a finite number of uniquely $K_r$-saturated graphs with no dominating vertex.