OFFSET
1,3
COMMENTS
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.
LINKS
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
EXAMPLE
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}
PROG
(Sage)
# 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)]
(PARI) \\ See PARI link in A350794 for program code.
A350360seq(15) \\ Andrew Howroyd, Jan 21 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Jim Snyder-Grant, Dec 26 2021
EXTENSIONS
Terms a(8) and beyond from Andrew Howroyd, Jan 21 2022
STATUS
approved