51 problems

TxGraffiti's conjecture. If $G \not\cong K_4$ and $\Delta(G)\leq 3$, then

For a graph $G$ on $n$ vertices, let $S(G)$ be the set of real symmetric matrices whose off-diagonal zero pattern is prescribed by adjacency in $G$. Define $mr(G)$ as the minimum r…

Let $G$ be a finite, simple, undirected graph. Write $g$ for its girth, $delta$ for its minimum degree, and $Z(G)$ for its zero forcing number, the minimum cardinality of a zero fo…

Let $G$ be a graph of order $n$, and let $\mathcal{F}_G$ denote the family of minimal forts of $G$. Minimal-forts lower-bound conjecture. The number of minimal forts satisfies … Th…

Let $G$ be a graph. The parameters $Z(G)$ and $Z_+(G)$ denote the standard and positive semidefinite zero forcing numbers of $G$, respectively. A graph is claw-free if it has no in…

Let $G$ be a connected graph. Let $Z(G)$ denote its zero forcing number, let $c(G)=\left\vert E(G)\right\vert-\left\vert V(G)\right\vert+1$ be its cyclomatic number, and let…

Let $G$ be a graph, let $n$ be its order, and let $\mathcal{F}_G$ denote the family of minimal forts of $G$. Let $\operatorname{Z}(G)$ denote the zero forcing number of $G$. Zero-f…

Let $G$ be a connected graph on $n$ vertices, and define the single-vertex expected propagation time by … Let $P_n$ denote the path on $n$ vertices. Narayanan–Sun's expected propag…

Narayanan–Sun's throttling conjecture. Every connected graph $G$ on $n$ vertices satisfies

Let $G$) be a graph, and let fixed propagation time equal to one mean that the minimum and maximum propagation times of minimum forcing sets are both one. The source defines standa…

For a graph $G$, the positive semidefinite propagation time interval is the interval of integers from the minimum to the maximum positive semidefinite propagation times of minimum…

Let $G$ be a connected graph. A PSD fast join is a graph of order $n\geq 2$ such that $G\cong K_n$ or … for $t\geq 2$ and positive integers $n_i,m_i$ with $n=\sum_{i=1}^t n_i+m_i$.…

Brimkov's conjecture. For every integer $d\geq 2$,

Let $ILT_l(G)$ denote the $l$-fold iterated line graph of a graph $G$, and let $Z(H)$ denote the zero forcing number of a graph $H$. Zero forcing conjecture for iterated line graph…

Strong non-automorphism conjecture. There are minimum zero forcing sets of $Q_d$ that are non-automorphic in a particularly strong sense.

Propagation-time interval conjecture. For every $d\geq 2$,

Let $T$ be a tree and let $G$ be a graph. The skew token exchange reconfiguration graph of $G$ is denoted by $\mathcal{Z}^{\mathrm{TE}}_-(G)$. Non-realizability conjecture. No tree…

Let $K_n$ be the complete graph on $n$ vertices and let $P_t$ be the path on $t$ vertices. Their direct product $K_n\times P_t$ has vertex set $V(K_n)\times V(P_t)$, with $(g,h)$ a…

Boyer et al.'s conjecture. For every graph $G$ on $n$ vertices,

Let $G_n$ be a family of graphs, and let $\mathcal{F}_{G_n}$ denote the family of minimal forts of $G_n$. The asymptotic growth rate is understood through the limit of successive r…

Let $G$ be a graph, and let a fort be a non-empty vertex subset such that no vertex outside the subset has exactly one neighbor in it. A fort is minimal if none of its proper subse…

Let $G$ and $G'$ be graphs, each containing an edge. The Cartesian-product zero forcing conjecture. … The conjecture would extend the sharp lower bound known when the maximum nulli…

Davila–Henning zero-forcing conjecture.

Let $G_n=K(n,2)$ be the Johnson graph whose vertices are the $2$-subsets of an $n$-element set, with two vertices adjacent when the corresponding subsets intersect in one element.…

Let $G$ be an $n$-vertex graph, and let $z(G;k)$ denote the number of zero forcing sets of $G$ having size $k$. Let $P_n$ be the path on $n$ vertices. Fixed-size zero forcing conje…