132 problems

Let $P_k$ and $P_m$ be paths on $k$ and $m$ vertices, respectively, and let $G=P_k\mathbin{\square}P_m$ denote their Cartesian product. For a graph $G$, write ${\mathbb D}(G)$ for…

Let $J_n(x)$ be a linear Jaco graph of order $n\geq1$. A diam-path is a path of diameter length, and let $P_d$ be a primary minimal dom-path, meaning a minimal path from $v_1$ to…

Let $J_\infty(x)$ be the infinite linear Jaco graph, and let $X$ be a $\gamma$-set, that is, a minimum dominating set. The vertex subscripts in the displayed set are…

Equality conjecture.

Let $G_{m,n}$ denote the $m$-by-$n$ grid graph, and let $\gamma_{\{2\}}(G_{m,n})$ be its integer $\{2\}$-domination number. The four-row grid conjecture. For every integer…

Let $G_{m,n}$ denote the $m$-by-$n$ grid graph, and let $\gamma_{\{2\}}(G_{m,n})$ be its integer $\{2\}$-domination number. The three-row grid conjecture. For every positive intege…

Let $G$ and $H$ be graphs. Their strong product $G\boxtimes H$ has vertex set $V(G)\times V(H)$, with two vertices $(g_1,h_1)$ and $(g_2,h_2)$ adjacent when either $g_1=g_2$ and…

Let $C_n$ denote the directed cycle of order $n$, and let $b3_I(D)$ be the Italian domination number of a digraph $D$. For an odd integer $n$, Kim's conjecture. … This conjecture c…

Let $G$ be a graph. A broadcast $f$ has positive-support vertices $V_f^+=\{v\in V(G):f(v)>0\}$ and strength-one vertices $V_f^1=\{v\in V(G):f(v)=1\}$. Write…

Akbari et al.'s conjecture.

Let $G$ be a finite simple graph. It is factor-critical if, for every vertex $v\in V(G)$, the graph $G-v$ has a perfect matching. The graph $G$ is $K_{1,5}$-free if it has no induc…

Let $G$ be a cubic graph, with domination number $\gamma(G)$ and isolation number $\iota(G)$. Domination–isolation ratio conjecture. For every cubic graph $G$, … The conjecture wou…

Cornet–Dravec–Torres conjecture. For every odd integer $n\ge 7$,

Characterization problem. Characterize those trees $T$ for which

Let $G$ be a finite simple undirected graph with vertex set $V(G)$, let $n=|V(G)|$, and let $d_k(G)$ denote the number of dominating sets of $G$ of size $k$. The polynomial … recor…

Stability characterization conjecture. For every integer $p\ge 1$,

EISPN path-product conjectures. If $k \ge 1$, then

Bipartite unique domination bound. If $G$ has a unique minimum dominating set, $\gamma\geq 2$, and $n\geq 3\gamma$, then its size $s(G)$ is bounded above by

Strong-product infinity conjecture. If

Let $G$ be a $k$-regular bipartite graph with bipartition $V(G)=A\cup B$ and $|A|=|B|=n$. Let $\gamma(G)$ be the domination number of $G$, and let $\rho_G$ denote its normalised do…

Tree upper-bound conjecture. If $3 \leq p \leq d$, then

For a graph $G=(V,E)$, a multipacking is a set $M\subseteq V$ such that, for every vertex $v\in V$ and every integer $k\geq 1$, $|N_k[v]\cap M|\leq k$, where $N_k[v]$ is the set of…

Kurz–Lätsch conjecture. For every bridgeless graph $G$ with $\gamma(G)=\gamma$,

Linear domination conjecture. There exists a constant $c>0$ such that for every $k$-fold cover $G$ of a graph $F$,

For a graph $G$, let ${\rm iso}(G,k)$ be the maximum number of pairwise disjoint $k$-clique isolating sets in a partition of $V(G)$, and let ${\rm iso}_c(G)$ be the analogous numbe…