Rooted graph

[6][7] However, in computer science, these terms commonly refer to a narrower notion; namely, a rooted directed graph is a digraph with a distinguished node r, such that there is a directed path from r to any node other than r.[8][9][10][11] Authors who give the more general definition may refer to graphs meeting the narrower definition as connected rooted digraphs[6] or accessible rooted graphs (see § Set theory).

The Art of Computer Programming defines rooted digraphs slightly more broadly, namely, a directed graph is called rooted if it has at least one node that can reach all the other nodes.

[13] Sometimes an additional restriction is added specifying that a flow graph must have a single exit (sink) vertex.

[22] Prime flow graphs are defined as flow graphs that cannot be decomposed via nesting or sequencing using a chosen pattern of subgraphs, for example the primitives of structured programming.

[24] Peter Aczel has used rooted directed graphs such that every node is reachable from the root (which he calls accessible pointed graphs) to formulate Aczel's anti-foundation axiom in non-well-founded set theory.

In this context, each vertex of an accessible pointed graph models a (non-well-founded) set within Aczel's (non-well-founded) set theory, and an arc from a vertex v to a vertex w models that v is an element of w. Aczel's anti-foundation axiom states that every accessible pointed graph models a family of (non-well-founded) sets in this way.

The number of rooted undirected graphs for 1, 2, ... nodes is 1, 2, 6, 20, 90, 544, ... (sequence A000666 in the OEIS).