13
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Do you really want an oriented cycle of length $exactly$ $k$? Or do you want an oriented cycle of length at most $k$? $\endgroup$ Dec 10, 2013 at 16:41

2 Answers 2

8
+250
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Thanks! I don't know about $K_{6,6}$, but $K_{7,7}$ is easy: Take the Fano plane and the dual Fano plane. For a point $p$ and a line $\ell$, put $p \to \ell$ if $p$ is on $\ell$ and $\ell \to p$ otherwise. Any two points are on a common line, and any two lines both miss some common point. I'm waiting a little bit on the bounty to see if anything more awesome turns up. $\endgroup$ Dec 10, 2013 at 16:22
  • $\begingroup$ @David Speyer It's too generous of you to give me the bounty. I only helped with a special case of your general question. $\endgroup$ Dec 11, 2013 at 13:22
  • $\begingroup$ Which was incredibly useful in clearing up my misconceptions. If another answer comes along to do the $k$-cycle case, I will certainly give it an additional bounty. $\endgroup$ Dec 11, 2013 at 13:23
6
$\begingroup$

The answer for Q1 is negative. Namely, even a strongly connected tournament may have large oriented diameter. Take the path $v_1\to v_2\to\dots\to v_n$ and connect $v_j\to v_i$ for all $i\leq j-2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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