A049512 -id:A049512 - cp's OEIS frontend

A350360 Number of unlabeled digraphs with n nodes containing a global sink (or source).

1, 1, 5, 60, 2126, 236560, 86140208, 105190967552, 442114599155408, 6536225731179398016, 345635717436525206325760, 66213119317905480992415271936, 46409685828045501628276172471067136, 119963222885004355352870426935849790038016

Offset: 1

Jim Snyder-Grant, Dec 26 2021

nonn

A global sink is a node that has out-degree zero and to which all other nodes have a directed path.

A global source is a node that has in-degree zero and has a directed path to all other nodes. A digraph with a global source, transposed, is a digraph with a global sink.

			For n=3, 5 digraph edge-sets: (vertex 0 is the single global sink)
  {10,21,20}
  {21,10}
  {21,12,10}
  {21,12,10,20}
  {20,10}

Andrew Howroyd, Table of n, a(n) for n = 1..50
Jim Snyder-Grant, C code to generate and count digraphs with global sinks
Eric Weisstein's World of Mathematics, Digraph Sink

The labeled version is A350792.
Row sums of A350797.
Cf. A051421, A049531.
Cf. A049512, A350415, A350794, A350798.

\\ See PARI link in A350794 for program code.
A350360seq(15) \\ Andrew Howroyd, Jan 21 2022

# A simple but slow way is to start from all digraphs and filter
# This code can get to n=5
# The linked C code was used to get to n=7
def one_global_sink(g):
    if (g.out_degree().count(0) != 1): return False;
    s = g.out_degree().index(0)
    return [g.distance(v,s) for v in g.vertices()].count(Infinity) == 0
[len([g for g in digraphs(n) if one_global_sink(g)]) for n in (0..5)]

Terms a(8) and beyond from Andrew Howroyd, Jan 21 2022

A003088 Number of unilateral digraphs with n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 11, 171, 8603, 1478644, 870014637

Offset: 0

N. J. A. Sloane

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 218.
Ronald C. Read, email to N. J. A. Sloane, 28 August, 2000.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. W. Robinson, Counting strong digraphs (research announcement), J. Graph Theory 1, 1977, pp. 189-190.

Cf. A057270, A003029 (labeled case), A003085, A035512, A051421, A049531, A049512.

Note that Read and Wilson incorrectly give a(4) as 172 - thanks to Vladeta Jovovic, Goran Kilibarda for finding this error and for verifying a(5).

a(7) from Sean A. Irvine, Jan 26 2015

A057279 Triangle T(n,k) of number of digraphs with a quasi-source on n unlabeled nodes and with k arcs, k = 0..n*(n-1).

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 3, 4, 4, 1, 1, 0, 0, 0, 7, 21, 37, 47, 38, 27, 13, 5, 1, 1, 0, 0, 0, 0, 18, 90, 309, 661, 1125, 1477, 1665, 1489, 1154, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 0, 44, 374, 1981, 7107, 19166, 41867, 77194, 122918, 170308, 206980, 220768, 207301, 171008, 124110, 78813, 43862, 21209, 8951, 3242, 1043, 288, 76, 17, 5, 1, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Table starts:
[1],
[0,1,1],
[0,0,3,4,4,1,1],
[0,0,0,7,21,37,47,38,27,13,5,1,1],
...
Number of digraphs with a quasi-source on 3 unlabeled nodes is 13=3+4+4+1+1.

Sean A. Irvine, Java program (github)
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

Row sums give A049512. Cf. A057270-A057278.

More terms from Sean A. Irvine, May 30 2022

cp's OEIS Frontend

A350360 Number of unlabeled digraphs with n nodes containing a global sink (or source).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Sage

Extensions

A003088 Number of unilateral digraphs with n unlabeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A057279 Triangle T(n,k) of number of digraphs with a quasi-source on n unlabeled nodes and with k arcs, k = 0..n*(n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions