Computing Metric and Connected Metric Dimension of Some Graphs

For a connected graph G=(V, E), a set of vertices B ⊆ V(G) resolves G if every vertex of G is uniquely determined by its vector of distances to the vertices in B. Mathematically: r(v | B) = (d(v, x₁), d(v, x₂), ..., d(v, xₖ)) is unique for every v in V(G). A metric basis B of G is connected if the subgraph induced by B is a nontrivial connected subgraph of G. The cardinality number of the connected metric basis is the connected metric dimension of G and is denoted cdim(G). We will introduce connected metric some graphs and proof them indexing, abstracting, and retrieval purposes. Also we proposing an approximate algorithm which finds a minimum connected metric dimension of a given graph.