Meeting walks on directed graphs

46 Views Asked by At

Consider a directed graph $G = (V,A)$. For every vertex $v \in V$ we have $d$ directed edges out of $v$, which we'll denote $v(1), v(2), \dots, v(d)$.

Given a sequence $i_1, i_2, \dots, i_\ell \in \{1, 2, \dots, d\}$ and a starting vertex $v$, there is a length-$\ell$ walk $v_0, v_1, \dots, v_\ell$ defined recursively:

  • $v_0 = v$.
  • for $1 \le k \le \ell$, from $v_{k-1}$, we take edge $v_{k-1}(i_k)$, and call its target $v_k$.

The question is: when can we guarantee that for any two vertices $x,y \in V$ there is a sequence $i_1, i_2, \dots, i_\ell \in \{1, 2, \dots, d\}$ such that the walks $x_0, x_1, \dots, x_\ell$ and $y_0, y_1, \dots, y_\ell$ meet (that is, such that $x_\ell = y_\ell$)?