Minimum diameter realizing a prescribed local ball

Definitions and mathematical statement

Fix integers $r\ge1$ and $d\ge2$, and a finite rooted graph $(B,o)$. Suppose there exists a finite connected graph $H$ such that, at every vertex $v\in V(H)$, the induced radius-$r$ ball rooted at $v$ is isomorphic to $(B,o)$. Assume the root has degree $d$. Such a realizing graph is necessarily $d$-regular.

Define \[ D(B,r)=\min\{\operatorname{diam}(H):H\text{ is finite and connected, and } (B_H(v,r),v)\cong(B,o)\text{ for all }v\}. \] The set is nonempty by hypothesis. Determine or effectively bound $D(B,r)$ from the local ball, and obtain useful bounds depending only on $d$ and $r$. In particular, for some fixed $d$, can one find realizable balls $B_j$ of radii $r_j\to\infty$ with \[ D(B_j,r_j)/r_j\longrightarrow\infty? \] Equivalently, can the minimum diameter forced by identical local neighborhoods grow faster than linearly with the neighborhood radius?

The isomorphisms preserve both roots and all edges of the induced balls. They are required at every vertex of the realizing graph, but the realizing graph need not be vertex-transitive. This minimizes over all finite realizations of one prescribed neighborhood, rather than measuring the diameter of an arbitrarily chosen realization, which could be unnecessarily large. At each fixed $d,r$ only finitely many candidate balls exist, so the requested general bounds concern their quantitative growth and not merely the finiteness of a maximum.

Short English statement

How large a diameter can be forced by requiring every local ball of a finite graph to equal one prescribed rooted ball?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 10000017 (AMR-099-0017), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Benjamini - Coarse Geometry and Randomness (Saint-Flour notes), Open problem 2.5, PDF page 22. Original source indexed by AMR-099-0017. https://www.wisdom.weizmann.ac.il/~itai/stflouraug24.pdf#page=22.
• S3 I. Benjamini, Coarse Geometry and Randomness, primary Saint-Flour notes; the numbered question and its surrounding definitions. https://arquivo.pt/noFrame/replay/20201231041548id_/http://www.wisdom.weizmann.ac.il/~itai/stflouraug24.pdf.
• S4 I. Benjamini, Euclidean vs. Graph Metric, primary numbered question and conventions. https://arquivo.pt/noFrame/replay/20201231041538id_/http://www.wisdom.weizmann.ac.il/~itai/erd100.pdf.