Jim Snyder-Grant - cp's OEIS frontend

User: Jim Snyder-Grant

Jim Snyder-Grant has authored 2 sequences.

A351052 Number of unlabeled digraphs with n nodes containing a global sink (or source), self-loops allowed.

1, 2, 18, 440, 32404, 7423456, 5473328160, 13430706072192, 113086387825668384, 3345639802029563258880, 353900830082830194441001984, 135600928084762756427776332541952, 190092581374833963606044859875698932736, 982736440685354936080688846774429648871161856

Offset: 1

Jim Snyder-Grant, Jan 30 2022

nonn

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

Jim Snyder-Grant, C code to generate and count digraphs with global sinks
Eric Weisstein's World of Mathematics, Digraph Sink

Cf. A350360 (self-loops not allowed).

// See Jim Snyder-Grant C code to generate and count digraphs with global sinks ./gsinks -l

\\ See PARI link in A350794 for program code.
seq(n)={Vec(InitiallyV(GraphCIData(n,DigraphWithLoopEdges)))} \\ Andrew Howroyd, Jan 30 2022

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

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

Original entry on oeis.org

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

cp's OEIS Frontend

User: Jim Snyder-Grant

A351052 Number of unlabeled digraphs with n nodes containing a global sink (or source), self-loops allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

C

PARI

Extensions