192 problems

A triangulated planar graph is a planar graph in which every face, including the outer face under the relevant convention, is a triangle; let $n$ denote its number of vertices and…

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

Let $G$ be a graph, and let $b(G)$ denote its bondage number and $\Delta(G)$ its maximum degree. Bondage number conjecture. The bondage number of a graph is at most its maximum deg…

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…

Two-thirds conjecture. Every twin-free isolate-free graph $G$ of order $n$ satisfies

Let $T_1$ and $T_2$ be trees of order at least $2$, and let $\gamma_{\mathrm{pr}}(T)$ denote the paired domination number of a graph $T$. Strict paired domination conjecture. … The…

Garijo's conjecture.

Verstraete's conjecture. If $g\geq 6$, then

Broadcast domination–multipacking conjecture. For every graph $G$,

Let $G$ be a graph in $\mathcal{C}$ and let $v\in V(G)$ be such that $G-v\in\mathcal{C}$. Vertex-deletion conjecture. … The conjecture proposes the missing lower bound from the cit…

Let $G$ and $H$ be graphs, let $G\times H$ denote their direct product, and write $i(G)$ for the independent domination number of $G$. Nowakowski–Rall's conjecture. For all graphs…

Let $G$ be a regular graph. Write the domination number of $G$ as $\gamma(G)$ and its edge domination number as $\gamma'(G)$. Baste, Fürst, Henning, Mohr and Rautenbach's conjectur…

Mynhardt–Roux's conjecture. For every $n\geq3$, $P_n$ is not an $\operatorname{IR}$-graph, and for every $n\geq5$, $C_n$ is not an $\operatorname{IR}$-graph.

Let $G$ be an undirected graph without twins, and let the location-domination number of $G$ be the minimum cardinality of a dominating set whose vertices have distinct neighborhood…

Rad–Volkmann conjecture. If $cDelta(G) cgeq 3$, then

Garijo, González and Márquez's conjecture. There exists an integer $n_1$ such that for any $n\geq n_1$, the maximum value of the location-domination number of a connected twin-free…

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 planar graph. Write $\rho(G)$ for its packing number and $\gamma(G)$ for its domination number. Ducz–Gujgiczer's conjecture. The bound … is optimal for planar graphs.…

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 monotonicity conjecture. For every $r\ge 3$ and every $n\ge 2r$,

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

Characterization problem. Characterize those trees $T$ for which

The S–SD equality conjecture. Given an SD-admissible graph $G$, it is NP-hard to decide whether

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