1
$\begingroup$

An oriented graph is a digraph without any self-loops, multiple arcs, or 2-cycles. What is the smallest minimum outdegree of an oriented graph on $n$ vertices that ensures there will always be a cycle of length at least $k$? Can the bound be improved if one includes the minimum indegree in the bound?

$\endgroup$
1
$\begingroup$

Out-degree $k-2$ is sufficient to force a directed cycle of length at least $k$. To see this, consider a longest directed path $P:=v_1v_2 \dots v_\ell$. Since $P$ is a longest path and there are no $2$-cycles, all out-neighbours of $v_\ell$ are among $\{v_1, \dots, v_{\ell-2}\}$. Since $v_\ell$ has at least $k-2$ out-neighbours, this gives a directed cycle of length at least $k$.

On the other hand, this bound cannot be improved too much. For example, out-degree $k$ is in general not strong enough to force a directed cycle of length $3k+1$. To see this, orient the complete multi-partite graph $K_{k,k,k}$ in the obvious way. Note that this example also has minimum in-degree $k$, so adding a minimum in-degree condition will not help too much.

$\endgroup$
  • $\begingroup$ Wait... I don't get how the out-neighbors of $P$ must be in the path. What if $P$ were a subgraph of a spanning tree of a non-Hamiltonian graph? Then wouldn't there always be an out-neighbor not in the path? $\endgroup$ – Elliot Gorokhovsky Dec 11 '16 at 5:27
  • $\begingroup$ Sorry, that was a typo. It should have read all out-neighbours of $v_\ell$. I edited it. $\endgroup$ – Tony Huynh Dec 11 '16 at 7:57
  • $\begingroup$ OK, it's clear now. $\endgroup$ – Elliot Gorokhovsky Dec 11 '16 at 8:33

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.