A characterization of some graphs with metric dimension two

DOI10.1142/S1793830917500276zbMATH Open1362.05111arXiv1509.02129OpenAlexW2963394749MaRDI QIDQ5347261FDOQ5347261

Ali Behtoei, Behnaz Omoomi, A. Davoodi, Mohsen Jannesari

Publication date: 23 May 2017

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Abstract: A set W subseteq V (G) is called a resolving set, if for each pair of distinct vertices u,v in V (G) there exists t in W such that d(u,t) eq d(v,t), where d(x,y) is the distance between vertices x and y. The cardinality of a minimum resolving set for G is called the metric dimension of G and is denoted by dim_M(G). A k-tree is a chordal graph all of whose maximal cliques are the same size k + 1 and all of whose minimal clique separators are also all the same size k. A k-path is a k-tree with maximum degree 2k, where for each integer j, k leq j < 2k, there exists a unique pair of vertices, u and v, such that deg(u) = deg(v) = j. In this paper, we prove that if G is a k-path, then dim_M(G) = k. Moreover, we provide a characterization of all 2-trees with metric dimension two.

Full work available at URL: https://arxiv.org/abs/1509.02129

Recommendations

• On path related graphs with constant metric dimension
• Resolvability in graphs and the metric dimension of a graph
• The metric dimension and metric independence of a graph
• \( [ 1 , 2 ]\)-dimension of graphs
• Characterization of \(n\)-vertex graphs with metric dimension \({n-3}\).

zbMATH Keywords

metric dimensionresolving setmetric basis\(k\)-tree

Mathematics Subject Classification ID

Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Cites Work

• Resolvability in graphs and the metric dimension of a graph
• On the Metric Dimension of Cartesian Products of Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Landmarks in graphs
• Metric bases in digital geometry
• On Metric Generators of Graphs
• Graphs with metric dimension two - a characterization
• Parallel recognition of series-parallel graphs
• Distances in random Apollonian network structures
• Characterization of \(n\)-vertex graphs with metric dimension \({n-3}\).

Cited In (13)

• Some classifications of graphs with respect to a set adjacency relation
• A Paley-like graph in characteristic two
• \( [ 1 , 2 ]\)-dimension of graphs
• A CHARACTERIZATION FOR METRIC TWO-DIMENSIONAL GRAPHS AND THEIR ENUMERATION
• A characterization of graphs \(G\) with \(G\cong K^ 2(G)\)
• Metric dimension of Andrásfai graphs
• A note on the metric and edge metric dimensions of 2-connected graphs
• Edge metric dimension and mixed metric dimension of a plane graph \(T_n\)
• Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension
• Further contributions on the outer multiset dimension of graphs
• Metric dimension of maximal outerplanar graphs
• Characterization of \(n\)-vertex graphs with metric dimension \({n-3}\).
• Computing vertex resolvability of some regular planar graphs

This page was built for publication: A characterization of some graphs with metric dimension two

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