The leafless vertex metric dimension bound conjecture

About 4 years old · traced to

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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.