Let $(V,E)$ be a graph and let $X_n$ be a random walk on the graph. At every step, the walker at $x$ jumps to one of the neighbors drawn uniformly at random among all the vertices $y$ such that there is a directed edge from $x$ to $y$.
What is the name of the most general class of graphs such that for any sequence of vertices $x_1$, $x_2$, $\ldots$, $x_n$, the next equality holds, $$P(X_1=x_1, X_2=x_2, \ldots X_n=x_n \, | \, X_0=x_0) = P(X_1=x_n, X_2=x_{n-1}, \ldots X_n=x_1 \, | \, X_0=x_n)$$ where $P (\, \cdot \, )$ is the probability law of the random walk? I would like to consider graphs with directed edges as well.
For example, on $\mathbb{Z}^d$ or on a tree the previous relation holds. If edges are directed such a relation might not hold any more, even if the graph is vertex-transitive.
First, the graph must be undirected (if it's directed and there exists an edge from $a$ to $b$ but not from $b$ to $a$, then if $X_1 = a$ and $X_2 = b$, it is impossible to have $X_{n-1} = b$ and $X_n = a$.
Let $d(x)$ be the out degree of node $x$:
$$P(X_i = x_1, \ldots, X_n = x_n | X_0 = x_0) = \prod_{i \in [0, n)} d(x_i)^{-1}$$
$$P(X_i = x_{n-1}, \ldots, X_n = x_0 | X_0 = x_n) = \prod_{i \in (0, n]} d(x_i)^{-1}$$
Thus if $P(X_i = x_{n-1}, \ldots, X_n = x_0 | X_0 = x_n) = P(X_i = x_1, \ldots, X_n = x_n | X_0 = x_0)$, we must have $d(x_0) = d(x_n)$. When $n=1$, it degrades to $d(x_0) = d(x_1)$ for every pair of nodes.
Thus, it's the class of all undirected graphs where all nodes in a connected component have equal out degree.