8
$\begingroup$

The following is a result of Erdős-Gallai from 1959 (https://link.springer.com/article/10.1007/BF02024498):

Given a 2-connected undirected unweighted graph with minimum degree at least $d$, for every pair of vertices $s$, $t$, there is an $(s,t)$-path of length at least $d$.

Is there a known extension of this theorem to directed graphs? In particular, is the answer to the following question known?

Given a 2-strongly-connected directed unweighted graph with minimum in- and out-degree at least $d$, is it the case that for every pair of vertices $s$, $t$, there is an $(s,t)$-path of length at least $d$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The answer to the question is no. In particular, the following is a counterexample for $d=3$:

counterexample for d=3

This counterexample can in fact be generalized to answer the question for $d \geq 3$ in the following way:

generalized counterexample

Basically, we have one bidirectional edge $s \leftrightarrow t$ and then $d - 1$ copies of the gadget on the right connected to it. Each of these gadgets has $d-2$ copies of a $(d+1)$-clique, all connected in the same way to the same vertices. Different gadgets use the same $s$ and $t$ but different copies of the other vertex that is not part of a clique.

Nicely enough, these counterexamples prevent paths from $s$ to $t$ of any length greater than $2$.

For $d < 3$ the statement is trivially true because the graph being $2$-strongly-connected implies that there must be a path of length $2$ from $s$ to $t$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.