The vertex metric dimension bound for connected graphs

About 4 years old · traced to

Let GG be a connected graph. The invariant L(G)L(G) is the graph parameter measuring the contribution of leaves, and c(G)c(G) is the cyclomatic number of GG. The vertex metric dimension bound conjecture.

dim(G)≤L(G)+2c(G).\mathrm{dim}(G)\leq L(G)+2c(G).

This extends the corresponding bound known for cactus graphs to all connected graphs. The source gives no resolution of the conjecture.

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.