论文标题
关键的Galton-Watson树和线性优先附着树的度量尺寸
The metric dimension of critical Galton-Watson trees and linear preferential attachment trees
论文作者
论文摘要
图$ g $的度量尺寸是$ g $的子集$ r $的最小尺寸，在报告其与遥远的（源）顶点$ v^\ star $的图形距离之后，在所有可能的$ g $的顶点中，启用了source vertex $ v^\ star $的唯一标识。在本文中，我们为某些树的公制尺寸显示了大量法律（LLN）：关键的Galton-Watson树，条件具有尺寸$ n $，并种植了一般的线性优先附件树。前类包括统一的随机树，后一类包括Yule-Trees（也称为随机递归树），$ M $ $ - AR的增加树木，二进制搜索树和积极的线性优先附件树。在所有这些情况下，我们都能明确识别LLN中的限制常数。我们的结果依赖于指标维度可以与子树属性相关的见解，因此我们可以利用Aldous和Janson等人开发的强大边缘树文献。
The metric dimension of a graph $G$ is the minimal size of a subset $R$ of vertices of $G$ that, upon reporting their graph distance from a distingished (source) vertex $v^\star$, enable unique identification of the source vertex $v^\star$ among all possible vertices of $G$. In this paper we show a Law of Large Numbers (LLN) for the metric dimension of some classes of trees: critical Galton-Watson trees conditioned to have size $n$, and growing general linear preferential attachment trees. The former class includes uniform random trees, the latter class includes Yule-trees (also called random recursive trees), $m$-ary increasing trees, binary search trees, and positive linear preferential attachment trees. In all these cases, we are able to identify the limiting constant in the LLN explicitly. Our result relies on the insight that the metric dimension can be related to subtree properties, and hence we can make use of the powerful fringe-tree literature developed by Aldous and Janson et al.
