The leafless-graph upper-bound conjecture for edge metric dimension

Let GG be a connected graph. Its edge metric dimension is denoted by edim(G)\mathrm{edim}(G), its cyclomatic number by c(G)=E(G)V(G)+1c(G)=|E(G)|-|V(G)|+1, and L(G)L(G) is the sum of the excess numbers of threads hanging at vertices. A graph is leafless when its minimum degree satisfies δ(G)2\delta(G)\geq2.

Leafless-graph upper-bound conjecture. Every leafless graph satisfies

edim(G)2c(G)1.\mathrm{edim}(G)\leq 2c(G)-1.

The paper proves this decreased bound for leafless cacti and for graphs with minimum degree at least three. Together with the analogous vertex statement, it is proposed as the sharp replacement for the earlier bound involving L(G)L(G); the general case remains open.

Sources & referencesView supporting material

Primary source

Jelena Sedlar and Riste Škrekovski, “Metric dimensions vs. cyclomatic number of graphs with minimum degree at least two”, arXiv:2108.09573 (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.