Cycle-rank conjecture for vertex metric dimension

About 5 years old · traced to

Let GG be a connected graph. Let L(G)L(G) denote the number of leaves, and let c(G)=∣E(G)∣−∣V(G)∣+1c(G)=\left\vert E(G)\right\vert-\left\vert V(G)\right\vert+1 be its cyclomatic number. The cycle-rank conjecture for vertex metric dimension.

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

The paper proves this bound for cactus graphs and notes that it also holds for 33-connected graphs; its validity for all connected graphs is left as a conjecture.

References

Primary source

Jelena Sedlar and Riste Škrekovski, “Vertex and edge metric dimensions of cacti”, arXiv:2107.01397 (2021).

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.