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

Max Alekseyev maxale at gmail.com
Fri Sep 28 04:23:45 CEST 2007


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.

Regards,
Max





More information about the SeqFan mailing list