Characterization of n-vertex graphs with metric dimension n-3.

DOI10.21136/MB.2014.143632MaRDI QIDQ2925938zbMATH OpenFDO

Authors Mohsen Jannesari, Behnaz Omoomi

Publication date 29 October 2014

Published in Mathematica Bohemica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.3588, http://hdl.handle.net/10338.dmlcz/143632

zbMATH Keywords

basismetric dimensionresolving set

Mathematics Subject Classification ID

Distance in graphs (05C12)

Abstract: For an ordered set $W=w_1,w_2,\mathrm{...},w_k$ of vertices and a vertex $v$ in a connected graph $G$, the ordered $k$-vector $r(v|W):=(d(v,w_1),d(v,w_2),\mathrm{...},d(v,w_k))$ is called the (metric) representation of $v$ with respect to $W$, where $d(x,y)$ is the distance between the vertices $x$ and $y$. The set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. The minimum cardinality of a resolving set for $G$ is its metric dimension. In this paper, we characterize all graphs of order $n$ with metric dimension $n-3$.

Review text

Let \(G\) be a connected graph and \(W=\{ w_1,w_2, \dots w_k \}\) an ordered set of vertices of \(G\). The ordered \(k\)-vector \(r(v| W):= \left( d(v,w_1), d(v,w_2), \dots, d(v,w_k)\right)\) is called the metric representation of the vertex \(v\) with respect to the set \(W\), where \(d(x,y)\) denotes the distance between vertices \(x\) and \(y\) in \(G\). A set \(W\) is called a resolving set for a graph \(G\) if distinct vertices of \(G\) have distinct metric representations with respect to \(W\). The minimum cardinality of a resolving set for \(G\) is called its metric dimension. In this paper, the authors completely characterize all graphs of order \(n\) with metric dimension \(n-3\). In the list of all possible graphs, they use a concept of the twin graphs and they show that all such twin graphs of graphs with metric dimension \(n-3\) have at most five vertices.

Recommendations

• On metric dimension of generalized Petersen graphs P(n,3).
• A characterization of some graphs with metric dimension two
• On local metric dimension of (n-3)-regular graph
• Characterization of M₃ (2)-graphs.
• Graphs with metric dimension two - a characterization
• Metrically homogeneous graphs of diameter \(3\)
• A characterization of distance-regular graphs with diameter three
• On three families of graphs with constant metric dimension
• A note on \(k\)-metric dimensional graphs
• On {ℓ}-Metric Dimensions in Graphs

Cited in

(23)

• Paths and metrics in a planar graph with three or more holes. I: Metrics
• Graphs of order n with determining number n-3
• Distance-based vertex identification in graphs: the outer multiset dimension
• On strong metric dimension of graphs and their complements
• On graphs of order \(n\) with metric dimension \(n-4\)
• Metric dimension for amalgamations of graphs
• On local metric dimension of (n-3)-regular graph
• Resolving domination in graphs
• All metric bases and fault-tolerant metric dimension for square of grid
• Metric dimension of Andrásfai graphs
• The characterization of caterpillars with multidimension 3
• A characterization of some graphs with metric dimension two
• On randomly \(k\)-dimensional graphs
• On lower bounds for the metric dimension of graphs
• On the metric representation of the vertices of a graph
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Metric dimension of lexicographic product of some known graphs
• Locating parameters of the total graph of \(\Gamma(\mathbb{Z}_{2^np^m})\)
• On dimension of some finite total graphs
• On metric dimension of some planar graphs with \(2n\) odd sided faces
• Resolving vertices of graphs with differences
• Improvements in nonlocal metric dimension bounds
• Breaking symmetry in graphs by resolving sets

This page was built for publication: Characterization of \(n\)-vertex graphs with metric dimension \({n-3}\).

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2925938)