TY - JOUR
T1 - Metric dimension of critical Galton–Watson trees and linear preferential attachment trees
AU - Komjáthy, Júlia
AU - Ódor, Gergely
N1 - Publisher Copyright:
© 2021 The Author(s)
PY - 2021/6
Y1 - 2021/6
N2 - 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 distinguished (source) vertex v⋆, enable unique identification of the source vertex v⋆ 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.
AB - 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 distinguished (source) vertex v⋆, enable unique identification of the source vertex v⋆ 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.
UR - http://www.scopus.com/inward/record.url?scp=85101411310&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2021.103317
DO - 10.1016/j.ejc.2021.103317
M3 - Article
AN - SCOPUS:85101411310
SN - 0195-6698
VL - 95
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103317
ER -