Suppose $G$ is a directed graph on $n$ vertices where all in-degrees and our-degrees are constant $d \geq 2$ (though the adjacency matrix need not be symmetric). Suppose further that the graph is strongly connected.

Since the graph is strongly connected, for any two vertices $v$ and $w$, there is a directed path connecting $v$ to $w$. I am curious about a different kind of path which isn't unidirectional, but "alternating" in a sense.

That is, is there a path $$v, u_1, u_2, u_3, \dots, u_{2t-1}, w$$ where $(u_1 \to v)$ is a directed edge, but $(u_1 \to u_2)$ is a directed edges, $(u_3 \to u_2)$ is a directed edge, $(u_3 \to u_4)$ is a directed edge, and so on. That is, $u_{2m-1}$ has two directed edges to $u_{2m-2}$ and $u_{2m}$.

So this is a kind of path between $v$ and $w$, but where the directions alternate in a sense.

My question: Is there always such a path connecting any two vertices of the directed graph $G$ which is strongly connected? If not, what properties are necessary for such a result to hold?

P.S. $G$ is not a directed cycle. Thanks to the comment for pointing that out.

  • 2
    $\begingroup$ In a cycle, every vertex has $d=1$ and the graph is obviously strongly connected. There is no "alternating" path, though. $\endgroup$ – Fabio Somenzi May 18 '18 at 15:16
  • $\begingroup$ @FabioSomenzi True, thats a trivial case which can be ignored. I have updated the question accordingly. $\endgroup$ – BharatRam May 18 '18 at 15:22
  • 1
    $\begingroup$ Directed cycle is not just a trivial example, but more like the most basic counterexample, in particular for any graph $G$ you can make $G' \supset G$ that does not have this property by adding some version/modification of a directed cycle to $G$. $\endgroup$ – dtldarek May 18 '18 at 15:30

Consider the following strongly connected digraph with $d=3$ and the problem of finding an alternating path from vertex $0$ to vertex $3$.

3-regular directed graph

Such a path must eventually use either edge $(0,2)$ or edge $(3,1)$. Let's call these two edges "bridges." All paths from $0$ back to itself that cross a bridge have even length and all similarly constrained paths from $0$ to $1$ have odd length. Hence no matter what alternating path is followed, it can never cross a bridge; hence it cannot connect $0$ to $3$.

EDIT: There is also a counterexample with $d=2$:

2-regular graph

From vertex $0$, alternating paths cannot reach vertex $2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.