48 problems

Metric dimension conjecture.

Let $G$ be a connected graph that is not a cycle. Write $O(G)=V(G)\cup E(G)$, let $\operatorname{dim_m}(G)$ denote the minimum cardinality of a mixed metric generator of $G$, let…

Ghalavand et al.'s conjecture.

Let $G$ be a graph on $n$ vertices with finite multiset dimension, where $\operatorname{dim}_{\mathrm m}(G)$ denotes the minimum cardinality of a multiset resolving set. Simanjunta…

Let $G$ be a graph of order $n(G)$ that admits a multiset resolving set. Its multiset dimension is denoted by $\operatorname{dim_{m}}(G)$. Hfidh's conjecture. … This conjecture ask…

Let $G$ be a graph of order $n(G)$, local metric dimension $\dim_l(G)$, and clique number $\omega(G)$. The hypothesis $n(G)\geq\omega(G)+1\geq 4$ is equivalent to considering graph…

Let $K_n\square K_m$ be the Cartesian product of complete graphs, with $n\ge 3$, $m\ge n+1$, and $3\le k\le 2n$. The weak $k$-metric dimension formula asserts that … This conjectur…

Maximum minimum-degree conjecture. The upper bound $3^{k-1}$ is sharp: for every $k$, there exists a graph $G$ of metric dimension $k$ whose minimum degree is $3^{k-1}$.

Metric-dimension conjecture. The metric dimension of the supertoken graph ${\cal F}_k(K_n)$ is

Ghalavand's conjecture. The local metric dimension of $G$ satisfies

Let $\Theta_{p,p+2,p}$ be the theta graph formed by three internally disjoint paths of lengths $p$, $p+2$, and $p$, respectively, where $p\geq 2$. Its metric dimension is denoted b…

Odd-cycle conjecture. For every odd integer $n\ge5$,

Let $G$ be a connected graph with minimum degree $\delta(G)\geq2$. A daisy graph is a graph consisting of at least two cycles sharing one vertex, and a petal is one of its cycles;…

Let $G$ be a graph distinct from the cycle $C_n$, with minimum degree $\delta(G)\geq2$. Here $\mathrm{dim}(G)$ denotes the vertex metric dimension and $c(G)$ the cyclomatic number.…

Let $G$ be a connected graph. The invariant $L(G)$ is the graph parameter measuring the contribution of leaves, and $c(G)$ is the cyclomatic number of $G$. The vertex metric dimens…

The conjecture. If

Let $k\ge 1$ be fixed, and let $m$ denote the parameter appearing in Proposition. Write $c_k$ for the leading coefficient of $m$ in that proposition. Leading-coefficient conjecture…

Let $G$ be a connected graph. Write $Z(G)$ for its zero forcing number, let $\dim(G)$ denote its metric dimension, and let $c(G)$ be the number of edges that must be removed from…

Leafless-graph upper-bound conjecture. Every leafless graph satisfies

Tree equidistant dimension conjecture.

Let $G$ be a connected graph. Let $L(G)$ denote the number of leaves, and let $c(G)=\left\vert E(G)\right\vert-\left\vert V(G)\right\vert+1$ be its cyclomatic number. The cycle-ran…

Let $G$ be a graph. The cycle-rank conjecture for vertex metric dimension. … Here $\mathrm{dim}(G)$ is the vertex metric dimension, $Z(G)$ is the zero forcing number, and…

For $r\geq 3$, let $BF(r)$ be the $r$-dimensional butterfly network, whose vertices are pairs $[s,j]$, where $s$ is an $r$-bit binary string and $j\in\{0,1,\ldots,r\}$. Let…

Let $G$ be a graph, let $c(G)$ be its cyclomatic number, let $L_1(G)$ be its number of leaves, and let $\mathrm{mdim}(G)$ be its mixed metric dimension. A cactus graph is a graph i…

Let $F_n$ be the folded $n$-cube obtained from the hypercube $Q_n$ by identifying each vertex $u$ with its antipode; write $\beta(F_n)$ for its metric dimension. Zhang's conjecture…