论文标题
在组成图的强度度上
On the strong metric dimension of composed graphs
论文作者
论文摘要
如果$ w $和包含$ v $的$ w $和$ u $之间的最短路径，或者含有$ w $之间的最短路径，则两个顶点$ u $和$ v $由顶点$ w $强烈解决。顶点套装$ r $是$ g $的强大解决方案，如果每对顶点有一个$ r $的顶点，可以强烈解决它们。 $ g $的强度度量尺寸是$ g $的最低强大解决方案的大小。我们表明，只有在可以有效地计算出每个双连接组件的最低强大分辨率设置时，才能有效地计算出无向图$ g $的最低强分解设置。
Two vertices $u$ and $v$ of an undirected graph $G$ are strongly resolved by a vertex $w$ if there is a shortest path between $w$ and $u$ containing $v$ or a shortest path between $w$ and $v$ containing $u$. A vertex set $R$ is a strong resolving set for $G$ if for each pair of vertices there is a vertex in $R$ that strongly resolves them. The strong metric dimension of $G$ is the size of a minimum strong resolving set for $G$. We show that a minimum strong resolving set for an undirected graph $G$ can be computed efficiently if and only if a minimum strong resolving set for each biconnected component of $G$ can be computed efficiently.
