digraph with fixed outdegree and no directed 1-, 2-, or 3-cycles

[franktaw at netscape.net]

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.



Franklin,

you should know about the file called  dexhis.txt

you can get to it by clicking on "More pages" then "All files"

It shows - at the end - what sequences have been retired and why

Here is the tail end:

...
A131705 (Andre) rifo A008973
A128921 (Schlicker) rifo A048909
A128918 (Schlicker) rifo A006244
A131747 (Choulet) rifo A001835
A131748 (Choulet) rifo A128917
A131749 (Choulet) rifo A006244
A131696 (anon) rifo A056542
A129589 (Bergot) rifo A104006
(rifo means "retired in favor of")

You can see that A129589 has been retired
(in fact the A-number has already been recycled)

Neil

> Is this some kind of typo?  The sequences are not at all similar; 
> searching, I don't find a duplicate for either one of them.
> 
> Franklin T. Adams-Watters
> 
> -----Original Message-----
> From: zak seidov <zakseidov at yahoo.com>
> 
> dupe: A129589==A104006