The cyclomatic-number bound for the difference between metric dimensions

From papers

Let GK2G\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.

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, “Bounds on metric dimensions of graphs with edge disjoint cycles”, arXiv:2010.10326 (2020).

Solutions 0

No solutions have been posted yet.