3
$\begingroup$

A graph $G$ is 1-walk-regular if

  1. for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ but not on $v$.
  2. for each edge $vw$ the number of walks of length $\ell$ starting in $v$ and ending in $w$ depends only on $\ell$, but not on $vw$.

I study a related class of bipartite graphs, where we still require property 2 but we replace property 1 by the following

  1. for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ and the bipartition class of $v$, but not on the choice of vertex in the bipartition class.

While 1-walk regular graphs encompass graphs that are both vertex- and edge-transitive, the latter class includes edge-transitive graphs that are not vertex-transitive (those graphs are always bipartite).

Question: Is this class of bipartite graphs (with properties 2 + 3) known? Does it have a name? Do you know examples of such graphs that are not edge-transitive?

$\endgroup$

0

You must log in to answer this question.