若干凸多胞体图的容错度量维数

Fault-Tolerant Metric Dimension of Some Convex Polytope Graphs

摘要: 图的容错度量维数的概念是由Hernand等人于2008年提出的，它是度量维数的一个新变形，也是图论和组合优化交叉研究的内容，在机器导航、医药化学、组合优化和图像处理等领域有着广泛的应用。由于图的容错度量维数比其度量维数有更好的适应性，所以图的容错度量维数的研究越来越受到人们的关注。对于给定的图和正整数k确定该图的容错度量维数是否不超过k是NP-难的。本文通过构作凸多胞体图$B_n$ ，$C_n$ 和$E_n$ 的容错解析集，得到了当$n\ge 6$ 时凸多胞体图$B_n$ ，$C_n$ 和$E_n$ 的容错度量维数都为4。这些成果在图论和组合优化中具有重要的理论价值，并在网络电信和图像处理等方面有重要应用。

Abstract: The concept of fault-tolerant metric dimension of a graph was introduced by Hernand et al. in 2008. It is a distortion of the metric dimension of a graph and is the intersection of graph theory and combinatorial optimization. It has been widely used in many fields, such as machine navigation, medicinal chemistry, combinatorial optimization and image processing. The study of fault-tolerant metric dimension of a graph gets more and more attention from people, since it has better adaptability than the metric dimension of a graph. For a given graph and a positive integer k, deciding whether its fault-tolerant metric dimension is less than or equal to k is an NP-complete problem. In this paper, by constructing the fault-tolerant resolving sets of convex polytope graphs $B_n$ , $C_n$ and $E_n$ , respectively, we obtain their fault-tolerant metric dimensions are all 4 for $n\ge 6$ . These results have theoretical value in graph theory and combinatorial optimization and have important applications in network telecommunications, image processing, etc.