Metric dimension of critical Galton-Watson trees and linear preferential attachment trees

DOI10.1016/j.ejc.2021.103317zbMath1466.05056arXiv2002.08503OpenAlexW3130698525MaRDI QIDQ2033923

Gergely Ódor, Júlia Komjáthy

Publication date: 18 June 2021

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.08503

zbMATH Keywords

binary search treeslocal limit theoryrandom tree model

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Distance in graphs (05C12) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Related Items

On the robustness of the metric dimension of grid graphs to adding a single edge ⋮ Sharp bound on the truncated metric dimension of trees ⋮ The power of adaptivity in source identification with time queries on the path

Uses Software

• Mathematica

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The difference between the metric dimension and the determining number of a graph
• Budgeted sensor placement for source localization on trees
• Metric dimension for random graphs
• Approximation complexity of metric dimension problem
• Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
• Asymptotic fringe distributions for general families of random trees
• On the determining number and the metric dimension of graphs
• The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance
• Resolvability in graphs and the metric dimension of a graph
• Locating the contagion source in networks with partial timestamps
• On the limiting distribution of the metric dimension for random forests
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Landmarks in graphs
• The degree sequence of a scale-free random graph process
• Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees
• Random Graphs and Complex Networks
• Approximability of the Minimum Weighted Doubly Resolving Set Problem
• Finding Adam in random growing trees
• Emergence of Scaling in Random Networks
• Base size, metric dimension and other invariants of groups and graphs
• Random Trees
• Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations
• On the convergence of supercritical general (C-M-J) branching processes
• Random Graph Isomorphism
• Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees
• Rumors in a Network: Who's the Culprit?