Return to Question

This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of which is still stumping me. I'll keep both parts of the question for the record, but the interesting part is after the second dividing line.

Let $G$ be a directed graph on $n$ vertices. For any vertices $u$ and $v$, let $\delta(u,v)$ be the length of the shortest directed path from $u$ to $v$ and let $d(u,v)$ be the length of the shortest path from $u$ to $v$ ignoring edge orientations. We will assume that $\delta(u,v)$ (and hence $d(u,v)$) if finite; the term for this is that the graph is strongly connected. I'll write $d=\max_{(u,v)} d(u,v)$ and $\delta = \max_{(u,v)} \delta(u,v)$.

Is there a bound for $\delta$ in terms of $d$, independent of $n$?

This question was answered in the negative by Ilya Bogdanov, below.

The question I can't answer:

Define a directed graph to have the pairwise domination property if, for any two distinct vertices $u$ and $v$ of $G$, there is a vertex $x$ with $u \rightarrow x \leftarrow v$. (In particular, this implies $d \leq 2$.) What I really need is:

Is there an integer $k$ such that every graph on $\geq 2$ vertices with the pairwise domination property contains an oriented cycle of length $\leq k$?

Note that it is enough to study strongly connected graphs here: If $G$ has the pairwise domination property, and $H$ is a strongly connected component of $G$ with no edges coming out of it, then $H$ also has the pairwise domination property.

In fact, I can't even prove or disprove the following (hence the bounty):

Does every graph on $\geq 2$ vertices with the pairwise domination property contain an oriented triangle?

This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of which is still stumping me. I'll keep both parts of the question for the record, but the interesting part is after the second dividing line.

Let $G$ be a directed graph on $n$ vertices. For any vertices $u$ and $v$, let $\delta(u,v)$ be the length of the shortest directed path from $u$ to $v$ and let $d(u,v)$ be the length of the shortest path from $u$ to $v$ ignoring edge orientations. We will assume that $\delta(u,v)$ (and hence $d(u,v)$) if finite; the term for this is that the graph is strongly connected. I'll write $d=\max_{(u,v)} d(u,v)$ and $\delta = \max_{(u,v)} \delta(u,v)$.

Is there a bound for $\delta$ in terms of $d$, independent of $n$?

This question was answered in the negative by Ilya Bogdanov, below.

The question I can't answer:

Define a directed graph to have the pairwise domination property if, for any two distinct vertices $u$ and $v$ of $G$, there is a vertex $x$ with $u \rightarrow x \leftarrow v$. (In particular, this implies $d \leq 2$.) What I really need is:

Is there an integer $k$ such that every graph on $\geq 2$ vertices with the pairwise domination property contains an oriented cycle of length $\leq k$?

Note that it is enough to study strongly connected graphs here: If $G$ has the pairwise domination property, and $H$ is a strongly connected component of $G$ with no edges coming out of it, then $H$ also has the pairwise domination property.

In fact, I can't even prove or disprove the following (hence the bounty):

Does every graph on $\geq 2$ vertices with the pairwise domination property contain an oriented triangle?

This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of which is still stumping me. I'll keep both parts of the question for the record, but the interesting part is after the second dividing line.

Let $G$ be a directed graph on $n$ vertices. For any vertices $u$ and $v$, let $\delta(u,v)$ be the length of the shortest directed path from $u$ to $v$ and let $d(u,v)$ be the length of the shortest path from $u$ to $v$ ignoring edge orientations. We will assume that $\delta(u,v)$ (and hence $d(u,v)$) if finite; the term for this is that the graph is strongly connected. I'll write $d=\max_{(u,v)} d(u,v)$ and $\delta = \max_{(u,v)} \delta(u,v)$.

Is there a bound for $\delta$ in terms of $d$, independent of $n$?

This question was answered in the negative by Ilya Bogdanov, below.

The question I can't answer:

Define a directed graph to have the pairwise domination property if, for any two distinct vertices $u$ and $v$ of $G$, there is a vertex $x$ with $u \rightarrow x \leftarrow v$. (In particular, this implies $d \leq 2$.) What I really need is:

Is there an integer $k$ such that every graph on $\geq 2$ vertices with the pairwise domination property contains an oriented $k$-cycle?

Note that it is enough to study strongly connected graphs here: If $G$ has the pairwise domination property, and $H$ is a strongly connected component of $G$ with no edges coming out of it, then $H$ also has the pairwise domination property.

In fact, I can't even prove or disprove the following (hence the bounty):

Does every graph on $\geq 2$ vertices with the pairwise domination property contain an oriented triangle?

This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of which is still stumping me. I'll keep both parts of the question for the record, but the interesting part is after the second dividing line.

Let $G$ be a directed graph on $n$ vertices. For any vertices $u$ and $v$, let $\delta(u,v)$ be the length of the shortest directed path from $u$ to $v$ and let $d(u,v)$ be the length of the shortest path from $u$ to $v$ ignoring edge orientations. We will assume that $\delta(u,v)$ (and hence $d(u,v)$) if finite; the term for this is that the graph is strongly connected. I'll write $d=\max_{(u,v)} d(u,v)$ and $\delta = \max_{(u,v)} \delta(u,v)$.

Is there a bound for $\delta$ in terms of $d$, independent of $n$?

This question was answered in the negative by Ilya Bogdanov, below.

The question I can't answer:

Define a directed graph to have the pairwise domination property if, for any two distinct vertices $u$ and $v$ of $G$, there is a vertex $x$ with $u \rightarrow x \leftarrow v$. (In particular, this implies $d \leq 2$.) What I really need is:

Is there an integer $k$ such that every graph on $\geq 2$ vertices with the pairwise domination property contains an oriented cycle of length $\leq k$?

Note that it is enough to study strongly connected graphs here: If $G$ has the pairwise domination property, and $H$ is a strongly connected component of $G$ with no edges coming out of it, then $H$ also has the pairwise domination property.

In fact, I can't even prove or disprove the following (hence the bounty):

Does every graph on $\geq 2$ vertices with the pairwise domination property contain an oriented triangle?

This question is an attempt to make progress on domotorp's interesting challenge. I'll first state the version of this which I would most expect to already be studied; then I'll state the version which would be enough for my purposes.

Let $G$ be a directed graph on $n$ vertices. For any vertices $u$ and $v$, let $\delta(u,v)$ be the length of the shortest directed path from $u$ to $v$ and let $d(u,v)$ be the length of the shortest path from $u$ to $v$ ignoring edge orientations. We will assume that $\delta(u,v)$ (and hence $d(u,v)$) if finite; the term for this is that the graph is strongly connected. I'll write $d=\max_{(u,v)} d(u,v)$ and $\delta = \max_{(u,v)} \delta(u,v)$.

Is there a bound for $\delta$ in terms of $d$, independent of $n$?

That's the one I'd expect to have already been studied by someone else. Here is what I actually need: Define a directed graph to have the pairwise domination property if, for any two distinct vertices $u$ and $v$ of $G$, there is a vertex $x$ with $u \rightarrow x \leftarrow v$. (In particular, this implies $d \leq 2$.) What I really need is:

Is there an integer $k$ such that every strongly connected graph on $> 2$ vertices with the pairwise domination property contains an oriented $k$-cycle?

A positive answer to the first question implies one for the second: If there is a directed path $u \leadsto v$ and a directed path $v \leadsto u$ both of length $\leq \delta$, then the union of these paths contains a directed cycle of length $\leq 2 \delta$.

A positive answer to this question shows that the parameter $\epsilon$, in domotrop's question, can't be taken less than $1/k$.

This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of which is still stumping me. I'll keep both parts of the question for the record, but the interesting part is after the second dividing line.

Let $G$ be a directed graph on $n$ vertices. For any vertices $u$ and $v$, let $\delta(u,v)$ be the length of the shortest directed path from $u$ to $v$ and let $d(u,v)$ be the length of the shortest path from $u$ to $v$ ignoring edge orientations. We will assume that $\delta(u,v)$ (and hence $d(u,v)$) if finite; the term for this is that the graph is strongly connected. I'll write $d=\max_{(u,v)} d(u,v)$ and $\delta = \max_{(u,v)} \delta(u,v)$.

Is there a bound for $\delta$ in terms of $d$, independent of $n$?

This question was answered in the negative by Ilya Bogdanov, below.

The question I can't answer:

Define a directed graph to have the pairwise domination property if, for any two distinct vertices $u$ and $v$ of $G$, there is a vertex $x$ with $u \rightarrow x \leftarrow v$. (In particular, this implies $d \leq 2$.) What I really need is:

Is there an integer $k$ such that every graph on $\geq 2$ vertices with the pairwise domination property contains an oriented $k$-cycle?

Note that it is enough to study strongly connected graphs here: If $G$ has the pairwise domination property, and $H$ is a strongly connected component of $G$ with no edges coming out of it, then $H$ also has the pairwise domination property.

In fact, I can't even prove or disprove the following (hence the bounty):

Does every graph on $\geq 2$ vertices with the pairwise domination property contain an oriented triangle?