dupe: A129589==A104006

[N. J. A. Sloane]

Dear Franklin,

This is a special case of the famous Caccetta H\"aggvist conjecture from
1978:

Conjecture: Every simple digraph on n vertices with outdegrees at least r,
has a directed cycle of length at most n/r.

The special case where n=3r, which coincides with your conjecture, has
received a lot of attention, but is still an open problem.
It is not even known if directed graphs with both in- and out-degrees at
least n/3 must have a directed triangle (or 2-cycle or loop)!

See for instance:

http://www.math.uiuc.edu/~west/openp/cacchagg.html
http://www.aimath.org/WWN/caccetta/caccetta.pdf

or google

"conjecture caccetta häggkvist"

Dion Gijswijt.


> Well, a(n) <= 3n+1.  Just arrange 3n+1 points on a circle,
> with each pointing at the next n points around the circle.
> So if your conjecture is correct, a(n) = 3n+1 (which is A016777).
>
> I suspect that this is the answer, but I have not been able to
> prove or disprove the conjecture.  (More precisely, I proved it
> twice and found three counter-examples, but all were flawed.)
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: Max Alekseyev <maxale at gmail.com>
>
> For given positive integer n, let a(n) be the minimum positive integer
> such that there exists a digraph on a(n) vertices with the outdegree
> of each vertex equal n and no directed 1- (i.e., self-loops), 2-, or
> 3-cycles.
>
> Does this sounds familiar to anybody? Is this sequence in OEIS?
>
> It seems that a(n)>3n but I have no proof yet.
>
> ________________________________________________________________________
> Check Out the new free AIM(R) Mail -- Unlimited storage and
> industry-leading spam and email virus protection.
>