23 problems

Vizing's conjecture. For all graphs $G$ and $H$, one has

Goddard–Henning conjecture. If

Domination conjecture for non-spherical surfaces. If $n$ is sufficiently large, then

Let $d\geq 2$, and let $G$ be a connected bipartite graph of order $n$. Write $C_{2d+2}$ for the cycle of length $2d+2$, and let $\mathcal{B}_d$ denote the graph family defined in…

Let $d\geq 1$ and let $T$ be a tree of order $n\geq d+1$. The $d$-distance independent domination number $\gamma_d^1(T)$ is the minimum size of a $d$-distance dominating set that i…

Minimum-degree-four paired-domination conjecture. The paired domination number satisfies $

Chen–Sun–Xing conjecture. The paired domination number satisfies $

Mixed weighted 2-kernel conjecture. In every digraph $G$, and for every map $f:V(G)\rightarrow\mathbb{Z}_+$, there is a 2-kernel $K$ such that

Weighted large 2-kernel conjecture. In every digraph $G$, and for every map $f:V(G)\rightarrow\mathbb{Z}_+$, there is a 2-kernel $K$ such that

Strongly connected $k$-kernel conjecture. For all integers $k\ge 3$, every strongly connected digraph $G$ has a $k$-kernel of size at most

Large 2-kernel conjecture. In every digraph $G$, there is a 2-kernel $K$ such that at least half the vertices of $G$ belong to $K$ or have an in-neighbour in $K$.

Domination conjecture for $SCC(2)$ graphs. If $G\in SCC(2)$, then

Polynomial-time decidability conjecture. This decision problem can be solved in polynomial time for any graph $G$.

Let $S$ be a spider, meaning a tree with one vertex of degree greater than $2$, whose legs all have length at most $3$. Let $S'$ be obtained from $S$ by deleting a leaf, and let…

Let $\gamma_{t,r}(G)$ be the $(t,r)$ broadcast domination number of a finite graph $G$. For finite graphs $G$ and $H$, the half-factor broadcast-domination conjecture. … This conje…

For a finite graph $G$, let $\gamma_{t,r}(G)$ denote its $(t,r)$ broadcast domination number. The paper has shown that the analogous bound fails for $r>1$, while its counterexample…

Let $G$ and $H$ be isolate-free graphs. For a graph $X$, let $\gamma_{t2}(X)$ denote its semi-total domination number, and let $G\,\Box\,H$ denote the Cartesian product of $G$ and…

Mim-width hardness conjecture. Every $\NP$-hard distance $(\sigma,\rho)$ problem is $\W[1]$-hard when parameterized by mim-width.

Let $\mathcal{K}_n=P_n\boxtimes P_n$ be the King grid, where $P_n$ is the path on $n$ vertices. Write $\gamma^*_e(G)$ for the minimum cardinality of an exponential dominating set i…

Let $C_m$ and $C_n$ be cycle graphs, and let $C_m\square C_n$ be their Cartesian product. Write $\gamma^*_e(G)$ for the minimum cardinality of an exponential dominating set in a gr…

Let $G$ be a graph of order at least $2$, with vertex set $V(G)$ and signed edge domination number $\gamma'_s(G)$, defined as the minimum weight of a signed edge dominating functio…

4-regular graph total [1,2]-domination conjecture. For any 4-regular graph $G$ of order $n$,

Cubic graph total [1,2]-domination conjecture. For any cubic graph $G$ of order $n$,