The cyclomatic-number bound for the difference between metric dimensions

About 6 years old · traced to

Let G≠K2G\ne K_{2} be a graph with cyclomatic number cc, defined by c=∣E(G)∣−∣V(G)∣+1c=|E(G)|-|V(G)|+1. Here, dim⁡(G)\dim(G) and edim⁡(G)\operatorname{edim}(G) denote the vertex and edge metric dimensions of GG, respectively.

Cyclomatic-number bound. For every such graph,

∣dim⁡(G)−edim⁡(G)∣≤c.\left\vert \dim(G)-\operatorname{edim}(G)\right\vert \leq c.

The bound is motivated by the corresponding equality for trees other than K2K_{2} and by the established result for unicyclic graphs. The claim proposes the analogous bound for graphs with higher cyclomatic number; the paper presents it as an ongoing conjectural direction.

References

Primary source

Jelena Sedlar and Riste Škrekovski, “Bounds on metric dimensions of graphs with edge disjoint cycles”, arXiv:2010.10326 (2020).

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.