Logo
All Random Solved Random Open
OPEN
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)$.

A problem of Erdős and Nešetřil. Erdős [Er88] wrote 'This problem seems to be interesting only if there is a nice expression for $h_t(d)$.'

It is easy to see that $h_t(d)\leq 2d^t$ always and $h_1(d)=d+1$.

Erdős and Nešetřil and Bermond, Bond, Paoli, and Peyrat [BBPP83] independently conjectured that $h_2(d) \leq \tfrac{5}{4}d^2+1$, with equality for even $d$. This was proved by Chung, Gyárfás, Tuza, and Trotter [CGTT90].

Cambie, Cames van Batenburg, de Joannis de Verclos, and Kang [CCJK22] conjectured that \[h_3(d) \leq d^3-d^2+d+2,\] with equality if and only if $d=p^k+1$ for some prime power $p^k$, and proved that $h_3(3)=23$. 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.\]

Additional thanks to: Ross Kang