Number of cyclic digraphs without sources nor sinks
Simone Severini
other words, cyclic digraps are non-acyclic digraphs.
In a digraph, a source is a vertex with in-set of size zero; a sink is
a vertex with out-set of size zero.
I would like to know the number of labeled cyclic digraphs on n
vertices without sources nor sinks.
Many thanks
Jim Nastos
> A cyclic digraph is a digraph in which every vertex is in a cycle. In
> other words, cyclic digraps are non-acyclic digraphs.
I'm not sure this is correct. The paw (a graph with 4 vertices, 3 of
them forming a triangle and the fourth vertex adjacent to exactly one of
those three) can be oriented with a cycle. This oriented paw is now a
non-acyclic digraph, but it is not the case that every vertex is in a
cycle.
Now, if you are just looking for non-acyclic digraphs, since there is
much work done on acyclic graphs, you can just subtract those off the
number of total digraphs. But I assume you want every vertex to be in a
cycle. Is this not equivalent to the digraph being "strongly connected" ?
> I would like to know the number of labeled cyclic digraphs on n
> vertices without sources nor sinks.
Do you want an exact formula in terms of n? Asymptotics? (Some
researchers are satisfied in saying that there are 2^O(f(n)) graphs on n
vertices. They also call this measure a "count" of the number of such
graphs, even though it is quite coarse.) Or maybe you are just looking for
the first few exact terms of the sequence?
J
Robert Israel
Simone Severini <seve...@cs.bris.ac.uk> wrote:
>A cyclic digraph is a digraph in which every vertex is in a cycle. In
>other words, cyclic digraps are non-acyclic digraphs.
>In a digraph, a source is a vertex with in-set of size zero; a sink is
>a vertex with out-set of size zero.
If a vertex is in a cycle, how could it be a source or sink?
>I would like to know the number of labeled cyclic digraphs on n
>vertices without sources nor sinks.
I can't give you an exact count, but there are some obvious bounds.
I assume you're talking about simple digraphs.
For a lower bound, consider all digraphs containing the cycle
1->2->3->...->n->1 which contains all vertices. Then
there are n(n-2) other possible directed edges, so there
are 2^(n(n-2)) labelled digraphs containing the given cycle, all
of which are cyclic.
For an upper bound, there are 2^(n(n-1)) labelled digraphs in
all.
The bounds are quite trivial, but the ratio (upper bound)/(lower bound)
is only 2^n which is small compared to the number.
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
Edwin Clark
"Jim Nastos" wrote
> On 25 Aug 2003, Simone Severini wrote:
>
> > A cyclic digraph is a digraph in which every vertex is in a cycle. In
> > other words, cyclic digraps are non-acyclic digraphs.
>
> I'm not sure this is correct. The paw (a graph with 4 vertices, 3 of
> them forming a triangle and the fourth vertex adjacent to exactly one of
> those three) can be oriented with a cycle. This oriented paw is now a
> non-acyclic digraph, but it is not the case that every vertex is in a
> cycle.
>
> Now, if you are just looking for non-acyclic digraphs, since there is
> much work done on acyclic graphs, you can just subtract those off the
> number of total digraphs. But I assume you want every vertex to be in a
> cycle. Is this not equivalent to the digraph being "strongly connected" ?
No. For example take two directed triangles and add a directed edge from one
vertex in one triangle to some vertex in the other triangle. Then every
vertex is contained in a directed cycle, but the graph is not strongly
connected.
The number of strongly connected digraphs on n nodes is a lower bound
however and this is known at least partially. Here's the entry from Sloane's
OEIS:
----------------------------------------------------------------------------
----
ID Number: A003030 (Formerly M5064)
URL: http://www.research.att.com/projects/OEIS?Anum=A003030
Sequence: 1,1,18,1606,565080,734774776,3523091615568,
63519209389664176,4400410978376102609280,
1190433705317814685295399296,
1270463864957828799318424676767488
Name: Strongly connected digraphs with n labeled nodes.
----------------------------------------------------------------------------
--
If I have this right the number of digraphs on n vertices for which every
vertex has indegree at least one and outdegree at least one is the same as
the number of n x n 0-1 matrices with zeros on the main diagonal and having
no all zero row and no all zero column. I calculate these numbers for n
from 1 to 4 to be: 0, 1, 18, 1699. This sequence I did not find in the
OEIS.
--Edwin Clark
Robert B. Israel
> In article <dcf1635f.03082...@posting.google.com>,
> Simone Severini <seve...@cs.bris.ac.uk> wrote:
> >A cyclic digraph is a digraph in which every vertex is in a cycle. In
> >other words, cyclic digraps are non-acyclic digraphs.
> >In a digraph, a source is a vertex with in-set of size zero; a sink is
> >a vertex with out-set of size zero.
> I can't give you an exact count, but there are some obvious bounds.
> I assume you're talking about simple digraphs.
Here's a better lower bound. Consider a random digraph on n vertices, where
each possible directed edge has probability 1/2 of being present, and all
are independent. The probability that a given vertex is in a 2-cycle
is 1 - (3/4)^(n-1). Using the FKG inequality, the probability that
all n vertices are in 2-cycles is at least (1 - (3/4)^(n-1))^n, which
is 1 - O(q^n) as n -> infinity if 3/4 < q < 1.
Thus the number of cyclic digraphs is at least
(1 - (3/4)^(n-1))^n 2^(n(n-1)).
Edwin Clark
"Simone Severini" <seve...@cs.bris.ac.uk> wrote in message
news:dcf1635f.03082...@posting.google.com...
The corresponding sequence is now in the OEIS as sequence number A086193
Brendan McKay and Vladeta Jovovic have given formulas:
Vladeta Jovovic's formula is
sum((-1)^(n-r)*binomial(n,r)*(2^(r-1)-1)^r*(2^r-1)^(n-r), r=0..n).
The first few values are:
0,1,18,1699,592260,754179301,3562635108438,
63770601591579079,4405870283636411477640,
1190873924687350003735546441,
1270602397076493907445608866890778,
5381240610642043789096251476993474339179
--Edwin Clark
V.Liskovets
> A cyclic digraph is a digraph in which every vertex is in a cycle.
In
> other words, cyclic digraps are non-acyclic digraphs.
> In a digraph, a source is a vertex with in-set of size zero; a sink
is
> a vertex with out-set of size zero.
>
> I would like to know the number of labeled cyclic digraphs on n
> vertices without sources nor sinks.
>
Here is a way to count labelled digraphs in which every node
belongs to a directed cycle (clearly they have neither sources
nor sinks).
Let K be a class of strongly connected digraphs (closed
wrt relabelling the nodes) and s_n(K) denote the number
of digraphs with n labelled nodes in it. a_n(K) denotes
the number of all digraphs with n nodes whose strong
components belong to K. Introduce the following formal
generating functions:
s(z,K):= sum_{n>0}s_n(K)z^n/n!,
a(z,K):= sum_{n>0}a_n(K)z^n/(n!2^{n(n-1)/2}),
u(z,K):= sum_{n>0}u_n(K)z^n/n! := 1-1/(1+a(z,K)) and
v(z,K):= sum_{n>0}v_n(K)z^n/n!, where
v_n(K):= 2^{n(n-1)/2}u_n(K).
Then the following general equation takes place:
s(z,K) = -log(1-v(z,K)) (*)
(see V.A.Liskovets, On a general enumerative scheme for
labelled graphs, Dokl. AN BSSR, 21:6 (1977), 496-499
(in Russian); MR58#21797). In particular for the class K = D
of ALL strongly connected digraphs (without loops and multiple
edges), _including_ the 1-node digraph [.], we have
s(z,D) = -log(1-v(z,D))
and
a_n(D) = 2^{n(n-1)} = #(all digraphs).
Thus,
a(z,D) = sum_{n>0}2^{n(n-1)/2}z^n/n!,
u(z,D) = sum_{n>0}u(n)z^n/n! = 1-1/(1+a(z,D)) and
v(z,D) = sum_{n>0}2^{n(n-1)/2}u_n(D)z^n/n!.
s_n(D) for n=1,2,3,... is the OEIS sequence
A003030 =_1_,1,18,1606,...
The digraph [.] is the ONLY type of strong components whose
nodes do not belong to any cycle. In order to exclude such
nodes, let us eliminate [.] from D and denote C:= D-{[.]}.
Then we have s(z,C) = s(z,D)-z. By (*),
s(z,C) = -log(1-v(z,C)), whence
v(z,C) = 1-exp(z-s(z,D)) = 1-exp(z+log(1-v(z,D)))
= 1-exp(z)(1-v(z,D)).
Now knowing v(z,C), we obtain
u(z,C) = sum_{n>0}v_n(C)z^n/(n!2^{n(n-1)/2}) and
a(z,C) = 1/(1-u(z,C))-1 = sum_{n>0}a_n(C)z^n/(n!2^{n(n-1)/2}).
The coefficients a_n(C) are the desired numbers of "cyclic"
digraphs: the ones in which all n labelled nodes belong to
(directed) cycles.
Numerically a_n(C) for n=1,2,3,... are 0,1,18,1699,587940,
750744901,... The difference a_4(C)-s_4(D) = 93 is verifiable
easily by hand, as well as A086193(5)-a_5(C) = 5*6*9*16 = 4320
(it's evident that a_4(C) = A086193(4)).
Btw, the acyclic digraphs can be counted in the same way
with 1-node components only: K:= {[.]}. Besides (curiously),
u_n(D) is the number of strong tournaments (A054946).
Valery Liskovets