Characterization of n-Vertex Graphs of Metric Dimension n − 3 by Metric Matrix

Mathematics

Yunlong Liu¹  Lianying Miao²  Juan Wang² 

[1] College of Information and Control Engineering, Weifang University, Weifang 261061, China;School of Mathematics, China University of Mining and Technology, Xuzhou 221116, China;

关键词: extremal graph;    metric dimension;    resolving set;    metric matrix;   

DOI  :  10.3390/math7050479

来源: DOAJ

【 摘 要 】

Let $G=\left(V\right(G),E(G\left)\right)$ be a connected graph. An ordered set $W\subset V\left(G\right)$ is a resolving set for G if every vertex of G is uniquely determined by its vector of distances to the vertices in W. The metric dimension of G is the minimum cardinality of a resolving set. In this paper, we characterize the graphs of metric dimension $n-3$ by constructing a special distance matrix, called metric matrix. The metric matrix makes it so a class of graph and its twin graph are bijective and the class of graph is obtained from its twin graph, so it provides a basis for the extension of graphs with respect to metric dimension. Further, the metric matrix gives a new idea of the characterization of extremal graphs based on metric dimension.

【 授权许可】

Unknown