Jelena Sedlar: Metric dimensions of graphs with edge disjoint cycles and generalizations

Jelena Sedlar: Metric dimensions of graphs with edge disjoint cycles and generalizations

Join Zoom Meeting
https://uni-lj-si.zoom.us/j/95260326742?pwd=YS9Mdkt0a2tZWXZOMC96NmhYUndIZz09

Meeting ID: 952 6032 6742
Passcode: 354823

Abstract. In a graph G, cardinality of the smallest ordered set of vertices that distinguishes every element of V(G) is the (vertex) metric dimension of G.  Similarly, the cardinality of such a set is the edge metric dimension of G, if it distinguishes E(G).  Finally, the mixed metric dimension of a graph G is the cardinality of the smallest set of vertices which distinguishes all pairs of elements from the set V(G) U E(G).

We first consider vertex and edge metric dimension of unicyclic graphs and prove that they obtain values from two particular consecutive integers, which can be determined from  the  structure  of  the  graph.   These  results  are  then  extended  to  graphs  with  edge  disjoint cycles.  A simple upper bound on the difference of these two metric dimensions is derived, which can easily be generalized and it is conjectured that it holds for all graphs, i.e.  even when cycles in a graph are not edge disjoint.  Considering further the two values that vertex and edge metric dimensions can take, we characterize when each of these two values is realized for each of the two metric dimensions.  

As for the mixed metric dimension, we determine the exact value of it for graphs with edge disjoint cycles.  This result yields an upper bound on mixed metric dimension, for which all extremal graphs are characterised within the considered class of graps.  As this upper bound can also be easily generalized, we conjecture that it holds for all graphs.  As a step towards solving this conjecture, we prove that the bound certainly holds for 3-connected graphs and that the bound can be attained only for graphs with vertex connectivity equal to 1 or 2. Besides already established extremal graphs within the class of graphs with edge disjoint cycles, we establish that the bound is also attained for balanced Theta graphs and we further conjecture these are the only graphs for which the bound is attained.

(joint work with Riste Škrekovski)