论文标题
关于2相连图的顶点和边缘度量维度的备注
Remarks on the vertex and the edge metric dimension of 2-connected graphs
论文作者
论文摘要
图G的顶点（分别边缘）度量尺寸是G中最小的顶点的大小，它区分了G中的所有顶点（resp。Edges），并且用dim（g）表示（resp。Edim（g））。上限DIM（G）<= 2C（G）-1和Edim（G）<= 2C（G）-1;其中C（g）表示G的循环数，以使仙人掌持有与循环不同的叶子，并且所有无叶仙人掌都表征了边界。进一步猜想，没有叶子的一般连接图的相同边界，并且通过证明该问题减少到2个连接图来支持此猜想。在本文中，我们将重点放在theta图上，作为与循环不同的最简单的2个连接图，并表明，theta图的两个度量尺寸的上限2C（g）-1保持，我们表征了所有绑定的绑定图。我们结论是，除了此处提到的已知的极端仙人掌和极端theta图外，在无叶图类别中没有其他极端图2C（g）-1的其他极端图。
The vertex (resp. edge) metric dimension of a graph G is the size of a smallest vertex set in G which distinguishes all pairs of vertices (resp. edges) in G and it is denoted by dim(G) (resp. edim(G)). The upper bounds dim(G) <= 2c(G) - 1 and edim(G) <= 2c(G)-1; where c(G) denotes the cyclomatic number of G, were established to hold for cacti without leaves distinct from cycles, and moreover all leafless cacti which attain the bounds were characterized. It was further conjectured that the same bounds hold for general connected graphs without leaves and this conjecture was supported by showing that the problem reduces to 2-connected graphs. In this paper we focus on Theta graphs, as the most simple 2-connected graphs distinct from cycle, and show that the the upper bound 2c(G) - 1 holds for both metric dimensions of Theta graphs and we characterize all Theta graphs for which the bound is attained. We conclude by conjecturing that there are no other extremal graphs for the bound 2c(G) - 1 in the class of leafless graphs besides already known extremal cacti and extremal Theta graphs mentioned here.
