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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Dec 8, 2016 at 0:47
-
$\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$ Commented Dec 11, 2016 at 5:27
-
$\begingroup$ Sorry, that was a typo. It should have read all out-neighbours of $v_\ell$. I edited it. $\endgroup$ Commented Dec 11, 2016 at 7:57
-