|
|
A350360
|
|
Number of unlabeled digraphs with n nodes containing a global sink (or source).
|
|
8
|
|
|
1, 1, 5, 60, 2126, 236560, 86140208, 105190967552, 442114599155408, 6536225731179398016, 345635717436525206325760, 66213119317905480992415271936, 46409685828045501628276172471067136, 119963222885004355352870426935849790038016
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|