论文标题
图的阈值维度
The Threshold Dimension of a Graph
论文作者
论文摘要
令$ g $为图，让$ u $，$ v $和$ w $为$ g $的顶点。如果$ u $和$ w $之间的距离不等于$ v $和$ w $之间的距离，则说$ w $可以解决$ u $和$ v $。 $ g $的度量尺寸，表示为$β（g）$，是最小的$ w $顶点的基数，因此每对$ g $的顶点都由$ w $的某些顶点解决。图$ g $的阈值尺寸，表示为$τ（g）$，是所有图形$ h $的最小度量尺寸，$ g $作为跨度子图。换句话说，$ g $的阈值维度是通过添加边缘从$ g $获得的所有图表中的最小度量维度。如果$β（g）=τ（g）$，则$ g $被称为\ emph {norryducible};否则，我们说$ g $是可还原的。如果$ h $是具有$ g $作为跨度子图的图形，并且$β（h）=τ（g）$，则$ h $称为$ g $的阈值图。 图的阈值维度是用最少数量的强大乘积表示，该路径的最小数量吸收了该图的某种类型的嵌入。建立了树木阈值尺寸的尖锐上限。还表明，不可约的树完全是公制尺寸的树。此外，如果$ t $是具有公制尺寸3或4的树，则$ t $具有阈值尺寸$ 2 $。在这两种情况下，可以通过分别将一个或两个边缘添加到$ t $来获得$ t $的阈值图。但是，这些结果并未扩展到具有度量尺寸$ 5 $的树木，即有公制尺寸的树$ 5 $，阈值尺寸超过$ 2 $。
Let $G$ be a graph, and let $u$, $v$, and $w$ be vertices of $G$. If the distance between $u$ and $w$ does not equal the distance between $v$ and $w$, then $w$ is said to resolve $u$ and $v$. The metric dimension of $G$, denoted $β(G)$, is the cardinality of a smallest set $W$ of vertices such that every pair of vertices of $G$ is resolved by some vertex of $W$. The threshold dimension of a graph $G$, denoted $τ(G)$, is the minimum metric dimension among all graphs $H$ having $G$ as a spanning subgraph. In other words, the threshold dimension of $G$ is the minimum metric dimension among all graphs obtained from $G$ by adding edges. If $β(G) = τ(G)$, then $G$ is said to be \emph{irreducible}; otherwise, we say that $G$ is reducible. If $H$ is a graph having $G$ as a spanning subgraph and such that $β(H)=τ(G)$, then $H$ is called a threshold graph of $G$. The threshold dimension of a graph is expressed in terms of a minimum number of strong products of paths that admits a certain type of embedding of the graph. A sharp upper bound for the threshold dimension of trees is established. It is also shown that the irreducible trees are precisely those of metric dimension at most 2. Moreover, if $T$ is a tree with metric dimension 3 or 4, then $T$ has threshold dimension $2$. It is shown, in these two cases, that a threshold graph for $T$ can be obtained by adding exactly one or two edges to $T$, respectively. However, these results do not extend to trees with metric dimension $5$, i.e., there are trees of metric dimension $5$ with threshold dimension exceeding $2$.
