论文标题
阈值维度和不可还原图
The Threshold Dimension and Irreducible Graphs
论文作者
论文摘要
令$ 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 $是不可约的。 我们给出了图形阈值维度的两个上限，这是直径的第一个尺寸，而第二个则在色数方面给出了两个上限。结果，我们表明$ n $的每个平面图都有阈值dimension $ o（\ log_2 n）$。我们表明，几个无限的图表家庭（已知具有公制尺寸$ 3 $）实际上是不可约的。最后，我们表明，对于任何整数$ n $和$ b $，带有$ 1 \ leq b <n $，有一个不可约的订单$ n $和公制尺寸$ b $的图。
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 $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 irreducible. We give two upper bounds for the threshold dimension of a graph, the first in terms of the diameter, and the second in terms of the chromatic number. As a consequence, we show that every planar graph of order $n$ has threshold dimension $O (\log_2 n)$. We show that several infinite families of graphs, known to have metric dimension $3$, are in fact irreducible. Finally, we show that for any integers $n$ and $b$ with $1 \leq b < n$, there is an irreducible graph of order $n$ and metric dimension $b$.
