The leafless vertex metric dimension bound conjecture

From papers

Let GG be a graph distinct from the cycle CnC_n, with minimum degree δ(G)2\delta(G)\geq2. Here dim(G)\mathrm{dim}(G) denotes the vertex metric dimension and c(G)c(G) the cyclomatic number. The leafless vertex metric dimension bound conjecture.

dim(G)2c(G)1.\mathrm{dim}(G)\leq2c(G)-1.

The bound is known for leafless cactus graphs, and the source proves it for Θ\Theta-graphs; the general case reduces to 2-connected graphs distinct from cycles and remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Martin Knor, Jelena Sedlar and Riste Škrekovski, “Remarks on the vertex and the edge metric dimension of 2-connected graphs”, arXiv:2203.07335 (2022).

Solutions 0

No solutions have been posted yet.