Cycle-rank conjecture for vertex metric dimension

From papers

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.

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

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

Solutions 0

No solutions have been posted yet.