Problem 934

Erdős Problem #934: declared status 'open'. Formalized: no. Let $h_t(d)$ be minimal such that every graph $G$ with $h_t(d)$ edges and maximal degree $\leq d$ contains two edges whose shortest path between them has length $\geq t$. Estimate $h_t(d)$. Current best: They also conjecture that, for all $t\geq 3$, $h_t(d)\geq (1-o(1))d^t$ for infinitely many $d$ and $h_t(d)\leq (1+o(1))d^t$ for all $d$ (where the $o(1)$ term $\to 0$ as $d\to \infty$). The same authors prove that, if $t$ is large, then there are infinitely many $d$ such that $h_t(d) \geq 0.629^td^t$, and that for all $t\geq 1$ we have$$h_t(d) \leq \tfrac{3}{2}d^t+1.$$ References [BBPP83] Bermond, J.-C. Prize: no. Tags: graph theory.