论文标题
图形的阈值强度
The Threshold Strong Dimension of a Graph
论文作者
论文摘要
让$ g $为连接的图形，$ u，v $和$ w $ $ g $。然后，如果有最短的$ u $ - $ w $路径，其中包含$ v $或最短的$ v $ - $ w $ - $ w $ - $ w $ to {\ em强烈解决} $ u $和$ v $，或者最短的$ v $ - $ w $路径包含$ u $。如果$ g $的每对顶点都通过$ w $的某些顶点强烈解析，则$ g $的$ w $顶点是{\ em strong stem set}。最小的强分辨率集合的图称为{\ em strong Basine}及其基数，表示为$β_S（g）$，$ g $的{\ em strong dimension}。图$ g $的{\ em阈值强尺寸}，表示为$τ_s（g）$，是所有具有$ g $的图形作为跨越子图的所有图。一个强度等于其阈值强维尺寸的图称为$β_S$ - {\ em norrydrible}。在本文中，我们建立了图形$ g $的阈值强度的几何表征，该图表以最小数量的路径（每种足够大的订单）表示，其强乘积可以容纳$ g $的某种类型的嵌入。我们证明，图的阈值强维不等于图图的先前研究的阈值维度。尺寸强的图表$ 1 $和$ 2 $一定是$β_S$ - irreducible。众所周知，唯一具有强度$ 1 $的图形是路径。我们完全描述了Oellermann和Peters-Fransen引入的强大解决图的强度$ 2 $的图形。我们获得了通用图的阈值强度的尖锐上边界，并确定了某些树木子类的确切值。
Let $G$ be a connected graph and $u,v$ and $w$ vertices of $G$. Then $w$ is said to {\em strongly resolve} $u$ and $v$, if there is either a shortest $u$-$w$ path that contains $v$ or a shortest $v$-$w$ path that contains $u$. A set $W$ of vertices of $G$ is a {\em strong resolving set} if every pair of vertices of $G$ is strongly resolved by some vertex of $W$. A smallest strong resolving set of a graph is called a {\em strong basis} and its cardinality, denoted $β_s(G)$, the {\em strong dimension} of $G$. The {\em threshold strong dimension} of a graph $G$, denoted $τ_s(G)$, is the smallest strong dimension among all graphs having $G$ as spanning subgraph. A graph whose strong dimension equals its threshold strong dimension is called $β_s$-{\em irreducible}. In this paper we establish a geometric characterization for the threshold strong dimension of a graph $G$ that is expressed in terms of the smallest number of paths (each of sufficiently large order) whose strong product admits a certain type of embedding of $G$. We demonstrate that the threshold strong dimension of a graph is not equal to the previously studied threshold dimension of a graph. Graphs with strong dimension $1$ and $2$ are necessarily $β_s$-irreducible. It is well-known that the only graphs with strong dimension $1$ are the paths. We completely describe graphs with strong dimension $2$ in terms of the strong resolving graphs introduced by Oellermann and Peters-Fransen. We obtain sharp upper bounds for the threshold strong dimension of general graphs and determine exact values for this invariant for certain subclasses of trees.
