This question is an attempt to make progress on [domotorp's interesting challenge](https://mathoverflow.net/questions/148466). 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](http://en.wikipedia.org/wiki/Strongly_connected_component). 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?
> 
> 
> 



Strongly connected directed graphs with large directed diameter and small undirected diameter?
Here's how to construct a counterexample to the last question.


It's quite easy to introduce a direction to the complete bipartite graph $K\_{6,6}$ such that (a) every vertex has outdegree $3$ and (b) the graph has the dominance property on pairs of *non-adjacent* vertices. One possible orientation of the $36$ edges is as follows:
$$\begin{bmatrix}
+ & + & + & - & - & -\\
+ & - & - & + & + & -\\
+ & - & + & - & - & +\\
- & + & - & + & - & +\\
- & + & - & - & + & +\\
- & - & + & + & + & -\\
\end{bmatrix}$$


(I left out the drawing, because it was too much of a mess.) This directed graph has no oriented triangles since it is bipartite.


Now replace every vertex in $K\_{6,6}$ with an oriented $4$-cycle, so the total number of vertices becomes $12 \times 4 =48$ (and the number of edges is $36 \times 16+4 \times 12=624$). The newly constructed graph has the dominance property on *all* pairs of vertices and also contains no oriented triangles.


